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
- Comptons, 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. Dobbs 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
- Gibbs 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
|