Table of Contents

## Index

A

  ACT (Archive Comparison Test), 25
  adaptive compression, 76-77, 527. See also adaptive Huffman coding
    dictionary-based compression, 203-207
      example (QIC-122), 204-207
    with graphic files, 325-326
  Adaptive Differential Pulse Code Modulation (ADPCM), 319, 527
  adaptive Huffman coding, 77-112
    algorithm for, 82
    code for, 88-89, 101-112
    compression program, 91, 101-112
    EncodeSymbol routine, 92-95
    escape code in, 83-84
    expand program, 91-92, 101
    incoming symbols, 100-101
    initialization of array, 89-90
    overflow problem with, 84-87
    rescaling, benefit of, 87-88
    swapping in, 81, 96-97
    symbols not used, coding space for, 82-83
    updating tree in, 77-80, 95-100
  adaptive modeling, 18-20, 155-162, 527. See also
  adaptive compression; adaptive Huffman coding
    compression in, 19
    decompression in, 19
  ADC. See analog-to-digital converter
  AddFileListToArchive() routine (CARMAN), 399-400
  Add files command (CARMAN), 382-383
  AddString() routine (LZSS), 235-238
  Adobe, 213
  ADPCM (Adaptive Differential Pulse Code Modulation), 319, 527
  affine functions, 462-463
  affine maps, 476-477
  AHUFF.C, 101-112
    statistics for, 512-514
  alphabets, 527
  American National Standards Institute (ANSI), 3
  analog-to-digital converter (ADC), 292-295, 311, 312
  ANSI (American National Standards Institute), 3
  ANSI C, 3-6
    prototyping in, 43-44
  Apple, 213-214, 298
  ARC (compression program), 24, 209, 210, 528
  Archive Comparison Test (ACT), 25
  archives, 527
  ARITH.C, 123, 136-152
    statistics for, 512-514
  ARITH-1.C., 156-162
    code for, 156-158
    escape code as fallback with, 159-161
    improvements to, 161-162
  ARITH-N.C, 163-200
    code for, 172-200
    escape possibilities, 164-165
    flush code for, 170
    memory and implementation of, 170
    order(-1) table for, 169
    order(-2) table for, 169-170
    potential improvements to, 171
    redesign of data structures for, 166-169
    scoreboarding with, 165-166
    statistics for, 512-514
    updating ARITH-1.C. for, 163-164
  arithmetic coding, 16-17, 114-152, 528
    code for, 123, 136-152
    compression program, 124-125, 136-152
    decoding process in, 116-117, 121-122, 133-136
    encoding process in, 114-116, 120-121, 130-133
    expansion program, 125-126
    floating-point math with, 118
    flushing encoder in, 133
    Huffman coding, advantages over, 113-114, 122-123
    initialization
    of encoder, 130
    of model, 126-130
    integer registers, using, 118-120
    output from, 114
    totals[] array, building, 130
    underflow, handling, 120-121
  ARJ (compression program), 24, 209, 210, 299-302, 381, 528
  Association for Shareware Professionals (ASP), 534-535
  AT&T, 290
  audio, digital. See digital audio
  average_boundaries() function (FRAC.C), 477

B

  Barnsley, Michael, 458-459, 462
  BITIO.C, 35-43
  BITIO.H, 36-38
  black cube, 298
  block coding, 528
  “blocky” images, 469
  Boss, Roger, 458, 510
  BuildFileList() routine (CARMAN), 393-394
  build_model() routine (arithmetic coding), 124, 127-128
  build_totals() routine (arithmetic coding), 130
  build_tree() (HUFF.C), 58

C

  C (programming language)
    issues in writing portable, 3-7
    reasons for using, 2-3
    versions of, 3
  CAR files, 382
    structure of, 384
  CARMAN, 381-455
    archive files, opening, 396-398
    CAR files in, 382, 384
    code, 408-455
    command-line processing in, 390-392
    command set, 382-383
    file list, generating, 392-396
    headers, 384-390
      CRC, header, 388-390
      storing, 385-388
    main processing loop of, 399-408
      extraction, file, 406-408
      input file, skipping/copying, 404-405
      insertion, file, 405-406
      workspace cleanup, 408
  CCITT (Consultive Committee for International Telegraph and Telephone), 22, 326, 528
  Central Point Software, 210
  CHEETAH.GS, 340, 375-379
  CHURN.C, 517-526
  classify_domains() function (FRAC.C), 474-475
  Cleary, John, 162
  codecs, 312-314
  codes, 528
  coding, 15-17, 528
    adaptive, 76-77
    modeling vs., 12-13
  Collage Theorem, 462
  color images, 344-345
    fractal compression of, 461
  COMPACT (compression program), 23, 529
  COMPAND.C, 314-318
  companding, 310-318
    code, 314-318
    codecs with, 312-314
    and linear conversion, 311-312
    and minimum resolution, 310-311
  compilers, 4
  COMPRESS (compression program), 23, 208, 529
    and LZW, 262
  compressed archive files, 381-382
  compress_init() function (FRAC.C), 473-474
  compression, lossy vs. lossless, 11-12
  compression algorithms
    adaptive Huffman coding, 91, 101-112
    arithmetic coding, 124-125, 136-152
    DCT.C, 346-348
    fractal compression, 461-467, 472
    LZ77, 216-218
    LZSS, 227, 231-242
      AddString() routine, 235-238
      DeleteString() routine, 238-240
      exit code, 235
      initialization, 232-233
      main loop, 233-235
      support routines, binary tree, 240-242
    LZW, 262-263, 270-271
  compression ratios, 7, 529
  compress_range() function (FRAC.C), 475-476
  Compton’s, 213
  Compuserve Information Service, 24, 210
  constants, in LZSS, 228-229
  Consultive Committee for International Telegraph and Telephone (CCITT), 22, 326, 528
  Contractive Mapping theorem, 460
  ContractNode() routine (LZSS), 240-241
  convert_int_to_symbol() routine
    arithmetic coding, 124-125, 131, 135-136
    statistical modeling, 160-161
  Cosine Transform Matrix, 333-335
  count_bytes() routine
    arithmetic coding, 128
    HUFF.C, 56
  CPT (compression program), 25
  CPU, and arithmetic coding, 16, 17
  Cyclical Redundancy Check (CRC), 529

D

  DAC. See digital-to-analog converter
  data structures, in highest-order modeling, 166-169
  DCLZ, 211
  DCT. See Discrete Cosine Transform
  DCT.C, 345-370
    code for, 357-370
    compression module, 346-348
    expansion algorithm, 353-354
    forward DCT routine, 349-350
    initialization of, 348-349
    input codes, 355-356
    OutputCode() routine, 351-353
    ReadDCTData() routine, 354-355
    WriteDCTData() routine, 350-351
  decode_string() routine (LZW), 272-273
  DecodeSymbol routine (adaptive Huffman coding), 91
  decompression algorithms
    adaptive Huffman coding, 91-92, 101
    arithmetic coding, 125-126
    DCT.C, 353-354
    fractal images, 467-469, 477
    LZ77, 218-219
    LZSS, 242-244
      potential improvements to, 243-244
    LZW, 264-270, 271-273
      implementation, 267
      tree maintenance and navigation, 268-270
      undefined code, problem with, 266-267
  Delete files command (CARMAN), 383
  DeleteString() routine (LZSS), 238-240
  dictionaries, 530
  dictionary-based compression, 20, 201-214
    adaptive methods with, 203-207
    example (QIC-122), 204-207
    ARC, 209
    COMPRESS (program), 208
    example of, 201-202
    general-purpose programs, 210-211
    with graphics files, 322-323
    hardware-specific programs, 211-212
    history of, 207-208
    patented software, 212-214
    static dictionaries, 202-203
  differentiation modulation, 324-325
  digital audio
    low-pass filters in, 293-294
    PC-based sound, 297-299
    and range of hearing, 290
    replay of sound, 293
    and sampling, 291-292, 294-297
    waveforms, 290-291
  Digital Signal Processor (DSP), 22
  digital-to-analog converter (DAC), 293, 295, 297, 311-312
  Discrete Cosine Transform (DCT), 22-23, 327-331, 529
    code, 357-370
    and entropy encoding, 343-344
    implementing, 332-333
    matrix multiplication, 333-335
    inverse, 330, 356-357
    output of, 335-336
    and quantization, 337-340
    sample program, utilizing, 345-370
      compression module, 346-348
      expansion algorithm, 353-354
      forward DCT routine, 349-350
      initialization, 348-349
      input DCT codes, 355-356
      input format, 346
      Inverse DCT, 356-357
      OutputCode() routine, 351-352
      ReadDCTData() routine, 354-355
      WriteDCTData() routine, 350-351
    two-dimensional, 330
    usefulness of, 331-332
    and zig-zag sequence, 341-343
  Discrete Fourier Transform, 335
  Disk Doubler, 211
  DOS, compression programs in, 23-24
  Dr. Dobb’s Journal, 7
  DSP. See Digital Signal Processor

E

  8-bit characters, 4
  encode_ symbol() routine
    adaptive Huffman coding, 91-95
    arithmetic coding, 131
  encoding, 528
  entropy, 13-14, 530
  entropy encoding, 343-344
  ERRHAND.C, 53-54
  ERRHAND.H, 53
  errors, quantization, 295
  escape codes, 530
    adaptive Huffman coding, 83-84
    ARITH-1.C., 159-161
    ARITH-N.C, 164-165
  expansion algorithms. See decompression algorithms
  Extract() routine (CARMAN), 405-408

F

  Fano, R. M., 27
  Fast Fourier Transform (FFT), 22, 327-329
  Fibonacci function, 84-85
  FIF (Fractal Image Format), 459
  filters, low-pass, 293-294
  find_map() function (FRAC.C), 476-477
  FindNextNode() routine (LZSS), 241-242
  finite-context modeling, 154
  first pass, 155
  Fisher, Yuval, 458, 510
  floating-point math, with arithmetic coding, 118
  flush_arithmetic_encoder() routine (arithmetic coding), 133
  flushing, with highest-order modeling, 170
  Forward DCT() routine, 349-350
  FRAC.C, 471-505
    classify_domains() function of, 474-475
    code, 477-505
    compress_init() function, 473-474
    compression results, 506-509
    compress_range() function of, 475-476
    find_map() function of, 476-477
    main compression module, 472-473
    traverse_image() function of, 477
  fractal image compression, 457-458
    decoding, 467-469
    history of, 457-459
    iterated function systems, 459-463
      image compression with, 461-467
      mathematics of, 460-461
    partitioned iterated function systems, 463-467
    patent concerns, 509-510
    and resolution independence, 469-471
    sample program, 471-509
      code, 477-505
      decompression module, 477
      domain classification in, 474-475
      image partitioning in, 475-476
      initialization function, 473-474
      main compression module, 472-473
      optimal affine maps, finding, 476-477
      results, compression, 506-509
  Fractal Image Format (FIF), 459
  FractInt program, 458
  freeware, 298-299, 530
  function body, 6-7
  function declarations, parameters in, 43-44
  function prototypes, 4-6

G

  G.721 algorithm, 318-319
  ghost buffers, 244
  Gibb’s phenomenon, 457
  GIF format, 210, 212-213
  Gilchrist, Jeff, 25
  global variables, in LZSS, 229-231
  Graphical User Interface (GUI), 321
  graphics compression
    fractal compression. See Fractal image compression
    lossy. See Lossy graphics compression
  Group 3 FAX, 530
  GS.C, 346
    code, 370-372
  GSDIFF.C, 372-375, 466-467
  GUI (Graphical User Interface), 321

H

  hard disk, and dictionary-based compression, 211
  hashing function (LZW), 268-269
  header CRC, 388-390
  headers, in CARMAN, 384-390
  hearing, range of, 290
  Hewlett-Packard, 211
  higher-order modeling, 153-154
  highest-order modeling, 162-170
    escape possibilities, 164-165
    flush code for, 170
    memory and implementation of, 170
    order(-1) and (-2) tables for, 169-170
    and redesign of data structures, 166-169
    scoreboarding with, 165-166
    updating ARITH-1.C. code for, 163-164
  HUFF.C
    code, 60-73
    command lines for, 74
    statistics for, 512-514
  HUFF-E, command lines for, 74
  Huffman, D. A., 15, 16, 531
  Huffman coding, 15, 54, 530-531. See also Adaptive Huffman coding
    advantages of arithmetic coding over, 122-123
    arithmetic coding vs., 16-17
    BITIO.C as illustration of, 35-43
    difficulties with, 113-114
    model of, 12-13
    probability table in, 75-76
    Shannon-Fano coding vs., 34-35
  Huffman table, 18
  Huffman tree, 18
    algorithm for building, 31-35
    building, 55-58
      counts, saving, 56-57
      symbols, counting, 56
    using, 59-60
  Hutchinson, J., 458

I

  IBM, 213-214, 297
  IDCT (Inverse DCT), 329-330, 356-357
  IFS. See Iterated Function Systems
  information theory, 13-15, 27, 531
  initialization
    adaptive Huffman coding, 89-90
    arithmetic coding, 126-130
    DCT.C, 348-349
    Discrete Cosine Transform, 348-349
    fractal image compression, 473-474
    LZSS, 232-233
  initialize_model() routine (adaptive Huffman coding), 76
    InitializeTree(tree) (adaptive Huffman coding), 90
  InitTree() (LZSS), 233
  input_counts() (HUFF.C), 57
  integer registers, with arithmetic coding, 118-120
  Intel, 298
  International Standards Organization (ISO), 22, 326, 338, 531
  International Telegraph and Telephone Consultative Committee (CCITT), 528
  Internet, 25, 298
  Inverse DCT (IDCT), 329-330, 356-357
  ISO. See International Standards Organization
  Iterated Function Systems (IFS), 459-467. See also Partitioned Iterated Function Systems
    image compression with, 461-467
    mathematics of, 460-461
  Iterated Systems, Inc., 458, 509-510

J

  Jacobs, Bill, 458, 510
  Jacquin, Arnaud, 458
  Joint Photographic Experts Group (JPEG), 22, 23, 326, 531. See also JPEG standard
  JPEG. See Joint Photographic Experts Group
  JPEG standard, 326-345
    coding, 340-345
    compression algorithm, 327
    Discrete Cosine Transform with, 327-340
    drawbacks of, 457
  Jung, Robert, 209

K

  Katz, Phil, 24
  K&R C, 3-7

L

  Lau, Raymond, 25
  League for Programming Freedom, 213
  Lehman, Bruce, 214
  Lempel, Abraham, 21, 207, 532, 536
  LHArc (compression program), 24, 209, 210, 531
  library function calls, 3-4
  LIFS (Local Iterated Function Systems), 459
  Linear Predictive Coding (LPC), 319, 532
  LISAW.GS, 464-471
  List files command (CARMAN), 383
  Local Iterated Function Systems (LIFS), 459
  lossless compression, 11-12, 532
    of sound, 299-302
  lossy compression (generally), 11, 22-23, 532
    of sound, 302-303
  lossy graphics compression, 321-379
    and adaptive coding, 325-326
    and differential modulation, 324-325
    JPEG standard for, 326-345
      coding, 340-345
      compression algorithm, 327
      Discrete Cosine Transform with, 327-340
      and quantization, 337-340
    results, analysis of, 375-379
    sample program, 345-370
      code, 357-370
      compression module, 346-348
      expansion algorithm, 353-354
      forward DCT routine, 349-350
      initialization, 348-349
      input DCT codes, 355-356
      input format, 346
      Inverse DCT, 356-357
      OutputCode() routine, 351-352
      ReadDCTData() routine, 354-355
      WriteDCTData() routine, 350-351
    statistical and dictionary compression vs., 322-323
    support programs, 370
      GS.C, 370-372
      GSDIFF.C, 372-375
  low-pass filters, 293-294
  LPC (Linear Predictive Coding), 319, 532
  LZ77, 21, 207-208, 209, 215-221, 532
    compression algorithm, 216-218
    decompression algorithm, 218-219
    as “greedy” algorithm, 226
    inefficiency of, 221
    limitations of, 255
    LZ78 vs., 256-257
    LZSS vs., 262
    problems with, 220-221
    and QIC-122, 205
    text window in, 215-216
  LZ78, 21-22, 207-208, 209, 255-262, 287-288, 532. See also LZW
    functioning of, 257-260
    implementation of, 260-262
    LZ77 vs., 256-257
    tree in, 260-261
  LZSS, 221-253, 532
    and ARJ 2.10, 300-301
    balanced trees, maintaining, 225-226
    binary tree in, 230-231
    and CARMAN, 383, 405
    code for, 244-253
    compression program, 227, 231-242
      AddString() routine, 235-238
      DeleteString() routine (LZSS), 238-240
      exit code, 235
      initialization, 232-233
      main loop, 233-235
      support routines, binary tree, 240-242
    constants in, 228
    data structures in, 222-225
    expansion program, 242-244
      potential improvements to, 243-244
    global variables in, 229-231
    as “greedy” algorithm, 226-226
    LZ77 vs., 262
    macros in, 228-229
    text window in, 221-222
  LZSS.C, 244-253
    statistics for, 512-514
  LZW, 208, 210, 212, 213, 262-288, 532
    code, 273-278
    compression program, 262-263, 270-271
    decompression program, 264-270, 271-273
      and LZW implementation, 267
      tree maintenance and navigation, 268-270
      undefined code, problem with, 266-267
    LZW15V.C as improvement of, 279
    patent concerns, 287-288
  LZW12.C
    code, 273-278
    decompression routine in, 271-273
    hashing function of, 268-269
    “special” nodes in, 270
    statistics for, 512-514
  LZW15V.C
    code, 280-287
    as improvement over LZW, 279
    statistics for, 512-514

M

  Macintosh, compression programs for, 24-25
  macros, in LZSS, 228-229
  MAIN-C.C, 45-50
  MAIN-E.C, 50-53
  MAIN.H, 45-46
  Mandelbrot, Benoit, 457, 458
  Mandelbrot set, 457-458
  MassageMSDOSFileName() routine (CARMAN), 394-396
  measurement of compression, 7
  Microcom Corp., 210
  Microsoft, 211, 213
  MNP-5, 210
  modeling, 17-18. See also adaptive modeling; highest-order modeling; Statistical modeling
    coding vs., 12-13
    finite-context, 154
    higher-order, 153-154
  models, 532
    static, 535
  modulation, differentiation, 324-325
  Moving Pictures Experts Group (MPEG), 22, 23, 532-533
  MPEG-II, 22
  MPEG (Moving Pictures Experts Group), 22, 23, 532-533
  MS-DOS, CARMAN with, 392-396

N

  NeXT Computer, 298
  nodes[] array, 88-89
  Nyquist, Harry, 295
  Nyquist Rate, 295, 533

O

  on-line services, 298
  OpenArchiveFiles() command, 397-398
  Oracle, 213
  order-0 modeling, 154
  order(-1) table (ARITH-N.C), 169
  order(-2) table (ARITH-N.C), 169
  order (of model), 533
  OutputBits routine (adaptive Huffman coding), 93
  OutputCode() routine (DCT.C), 351-353
  output_counts() routine
    arithmetic coding, 129
    HUFF.C, 57
  overflow, in adaptive Huffman coding, 84-87

P

  p x 64, 533-534
  P6 processor (Intel), 298
  parameters, in function declarations, 43-44
  ParseArguments() routine (CARMAN), 390-391
  Partitioned Iterated Function Systems (PIFS), 458, 467, 509
    compression with, 463-467
  patent concerns
    dictionary-based compression programs, 212-214
    fractal image compression, 509-510
    LZW algorithm, 287-288
  PC Backup, 210
  PC-based sound, 297-299
  PCX format, 322
  phrases, 533
  PIFS. See Partitioned Iterated Function Systems
  PKWare, 24
  PKZ204.EXE, 24
  PKZIP, 24, 209, 210, 381, 533
  PNG format, 209, 213
  Print files command (CARMAN), 383
  probability table (Huffman coding), 75-76
  prototypes, 43-44
  pseudocode, 2

Q

  QIC-122, 205-207, 211, 212
  quality factor, 345
  quantization, 337-340
    errors in, 295
    matrix for, 338-340

R

  Radford, Neal, 161
  ReadDCTData() routine, 354-355
  redundancy, 13
  redundant information, 13
  refine_image() function (FRAC.C), 477
  Replace files command (CARMAN), 383
  rescaling, in adaptive Huffman coding, 87-88
  resolution independence, 469-471
  RLE (Run-Length Encoding), 341, 534
  root mean square (RMS), 346, 466-467, 507
  Run-Length Encoding (RLE), 341, 534

S

  SAMPLE-3.RAW., 301
  sampling, 291-292
    of variables, 294-297
  scale_counts() routine (arithmetic coding), 128-129
  scoreboarding, with highest-order modeling, 165-166
  second pass, 155
  Shannon, Claude, 13, 14, 27, 202, 534
  Shannon-Fano coding, 15, 27-29, 534
    Huffman coding vs., 34-35
  Shannon-Fano tree, 28-29, 32
    algorithm for building, 29-31
  shareware, 298-299, 534-535
  SILENCE.C, 305-309
  silence compression, 303-310
    code, 305-309
    effectiveness of, 310
  16-bit machines, 4
  sliding window compression. See LZ77; LZSS
  Sloan, Alan, 458-459
  Sound Blaster, 298
  speech compression, 289-319
    ADPCM algorithm, 319
    companding, 310-318
      code, 314-318
      codecs with, 312-314
      linear conversion with, 311-312
      and minimum resolution, 310-311
    and digital audio, 289-299
      low-pass filters, 293-294
      PC-based sound, 297-299
      range of hearing, 290
      replay, 293
      sampling, 291-292
      variables, sampling, 294-297
      waveforms, 290-291
    G.721 algorithm, 318-319
    Linear Predictive Coding, 319
    lossless compression, 299-302
    lossy compression, 302-303
    silence compression, 303-310
      code, 305-309
      effectiveness of, 310
  SQ program, 23, 535
  Stac Electronics, 204-205, 210, 211, 213
  Stacker, 211
  static dictionary-based compression, 20, 202-203
  static models, 535
  statistical modeling, 14, 18-20, 153-200
    and adaptive compression, 155-162
      escape code as fallback, using, 159-161
      example (ARITH-1.C.), 156-158
      improvements to, 161-162
    and finite-context modeling, 154
    with graphics files, 322
    and higher-order modeling, 153-154
    highest-order modeling (ARITH-N.C), 162-170
      code, 172-200
      data structures, redesign of, 166-169
      escape probabilities, 164-165
      flush code for, 170
      implementation, memory and, 170
      order(-1) table for, 169
      order(-2) table for, 169-170
      scoreboarding with, 165-166
      updating ARITH-1.C for, 163-164
    potential improvements to, 171
  statistics, compression, 7, 511-515
  __STDC__ macro, 74
  StuffIt (compression program), 25
  swap_nodes() routine (adaptive Huffman coding), 82
  swapping, in adaptive Huffman coding, 81, 96-97
  switching equipment, 290
  symbols, 535

T

  TAR, 24, 535-536
  Test files command (CARMAN), 383
  test program (CHURN.C), 517-526
  text windows
    LZ77, 215-216
    LZSS, 221-222
  32-bit machines, 4
  time domain representation, 328
  tokens, 536
  traverse_image() function (FRAC.C), 477
  tree(s). See also Huffman tree
    in LZ78, 260-261
    in LZSS, 225-226, 230-231
    in LZW, 268-270
    updating, in adaptive Huffman coding, 77-80, 95-100

U

  underflow, 120-121, 132-133
  Unisys, 209, 212, 287
  UNIX, 4
    CARMAN with, 392-393
    compression programs in, 23
    dictionary-based compression with, 208, 209
  update exclusion, 163-164
  UpdateModel() routine (adaptive Huffman coding), 76, 77, 91-92
  U.S. Patent Office, 213-214
  utility programs, 298-299

V

  V.4bis, 212
  V.42bis, 211
  variables, sampling, 294-297
  vector quantization, 457, 463-467
  VGA display, 321, 346
  VOC-HDR.EXE, 298

W

  waveforms, 290-291
  Welch, Terry, 208, 209, 212, 287, 536
  WinZIP, 24
  Witten, Ian H., 161
  World-Wide Web, 298
  WriteDCTData() routine, 350-351
  WriteFileHeader() routine (CARMAN), 388

X

  Xtract files command (CARMAN), 383

Y

  Yoshizaki, Haruyasu, 24, 209

Z

  zig-zag sequence, 341-343
  ZIP files, 24, 25
  ZipIt V1.2, 25
  Ziv, Jacob, 21, 207, 532, 536

Table of Contents