home *** CD-ROM | disk | FTP | other *** search
view JSON data
|
view as text
|
open on a Mac
|
open on a PC
This file was processed as: SHell self-extracting ARchive
(archive/shar).
You can browse this item here: part02
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| ASCII text
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000010| 2e 73 6f 75 72 63 65 73 | 2e 6d 69 73 63 0a 46 72 |.sources|.misc.Fr|
|00000020| 6f 6d 3a 20 6a 70 65 67 | 2d 69 6e 66 6f 40 75 75 |om: jpeg|-info@uu|
|00000030| 6e 65 74 2e 75 75 2e 6e | 65 74 20 28 49 6e 64 65 |net.uu.n|et (Inde|
|00000040| 70 65 6e 64 65 6e 74 20 | 4a 50 45 47 20 47 72 6f |pendent |JPEG Gro|
|00000050| 75 70 29 0a 53 75 62 6a | 65 63 74 3a 20 20 76 33 |up).Subj|ect: v3|
|00000060| 34 69 30 35 36 3a 20 20 | 6a 70 65 67 20 2d 20 4a |4i056: |jpeg - J|
|00000070| 50 45 47 20 69 6d 61 67 | 65 20 63 6f 6d 70 72 65 |PEG imag|e compre|
|00000080| 73 73 69 6f 6e 2c 20 50 | 61 72 74 30 32 2f 31 38 |ssion, P|art02/18|
|00000090| 0a 4d 65 73 73 61 67 65 | 2d 49 44 3a 20 3c 31 39 |.Message|-ID: <19|
|000000a0| 39 32 44 65 63 31 37 2e | 30 34 31 34 30 30 2e 32 |92Dec17.|041400.2|
|000000b0| 32 35 35 35 40 73 70 61 | 72 6b 79 2e 69 6d 64 2e |2555@spa|rky.imd.|
|000000c0| 73 74 65 72 6c 69 6e 67 | 2e 63 6f 6d 3e 0a 58 2d |sterling|.com>.X-|
|000000d0| 4d 64 34 2d 53 69 67 6e | 61 74 75 72 65 3a 20 35 |Md4-Sign|ature: 5|
|000000e0| 61 33 30 38 61 63 61 63 | 34 66 63 32 66 30 38 38 |a308acac|4fc2f088|
|000000f0| 31 65 30 65 32 30 61 30 | 37 64 31 31 38 34 39 0a |1e0e20a0|7d11849.|
|00000100| 44 61 74 65 3a 20 54 68 | 75 2c 20 31 37 20 44 65 |Date: Th|u, 17 De|
|00000110| 63 20 31 39 39 32 20 30 | 34 3a 31 34 3a 30 30 20 |c 1992 0|4:14:00 |
|00000120| 47 4d 54 0a 41 70 70 72 | 6f 76 65 64 3a 20 6b 65 |GMT.Appr|oved: ke|
|00000130| 6e 74 40 73 70 61 72 6b | 79 2e 69 6d 64 2e 73 74 |nt@spark|y.imd.st|
|00000140| 65 72 6c 69 6e 67 2e 63 | 6f 6d 0a 0a 53 75 62 6d |erling.c|om..Subm|
|00000150| 69 74 74 65 64 2d 62 79 | 3a 20 6a 70 65 67 2d 69 |itted-by|: jpeg-i|
|00000160| 6e 66 6f 40 75 75 6e 65 | 74 2e 75 75 2e 6e 65 74 |nfo@uune|t.uu.net|
|00000170| 20 28 49 6e 64 65 70 65 | 6e 64 65 6e 74 20 4a 50 | (Indepe|ndent JP|
|00000180| 45 47 20 47 72 6f 75 70 | 29 0a 50 6f 73 74 69 6e |EG Group|).Postin|
|00000190| 67 2d 6e 75 6d 62 65 72 | 3a 20 56 6f 6c 75 6d 65 |g-number|: Volume|
|000001a0| 20 33 34 2c 20 49 73 73 | 75 65 20 35 36 0a 41 72 | 34, Iss|ue 56.Ar|
|000001b0| 63 68 69 76 65 2d 6e 61 | 6d 65 3a 20 6a 70 65 67 |chive-na|me: jpeg|
|000001c0| 2f 70 61 72 74 30 32 0a | 45 6e 76 69 72 6f 6e 6d |/part02.|Environm|
|000001d0| 65 6e 74 3a 20 55 4e 49 | 58 2c 20 56 4d 53 2c 20 |ent: UNI|X, VMS, |
|000001e0| 4d 53 2d 44 4f 53 2c 20 | 4d 61 63 2c 20 41 6d 69 |MS-DOS, |Mac, Ami|
|000001f0| 67 61 2c 20 41 74 61 72 | 69 2c 20 43 72 61 79 0a |ga, Atar|i, Cray.|
|00000200| 53 75 70 65 72 73 65 64 | 65 73 3a 20 6a 70 65 67 |Supersed|es: jpeg|
|00000210| 3a 20 56 6f 6c 75 6d 65 | 20 32 39 2c 20 49 73 73 |: Volume| 29, Iss|
|00000220| 75 65 20 31 2d 31 38 0a | 0a 23 21 20 2f 62 69 6e |ue 1-18.|.#! /bin|
|00000230| 2f 73 68 0a 23 20 54 68 | 69 73 20 69 73 20 61 20 |/sh.# Th|is is a |
|00000240| 73 68 65 6c 6c 20 61 72 | 63 68 69 76 65 2e 20 20 |shell ar|chive. |
|00000250| 52 65 6d 6f 76 65 20 61 | 6e 79 74 68 69 6e 67 20 |Remove a|nything |
|00000260| 62 65 66 6f 72 65 20 74 | 68 69 73 20 6c 69 6e 65 |before t|his line|
|00000270| 2c 20 74 68 65 6e 20 66 | 65 65 64 20 69 74 0a 23 |, then f|eed it.#|
|00000280| 20 69 6e 74 6f 20 61 20 | 73 68 65 6c 6c 20 76 69 | into a |shell vi|
|00000290| 61 20 22 73 68 20 66 69 | 6c 65 22 20 6f 72 20 73 |a "sh fi|le" or s|
|000002a0| 69 6d 69 6c 61 72 2e 20 | 20 54 6f 20 6f 76 65 72 |imilar. | To over|
|000002b0| 77 72 69 74 65 20 65 78 | 69 73 74 69 6e 67 20 66 |write ex|isting f|
|000002c0| 69 6c 65 73 2c 0a 23 20 | 74 79 70 65 20 22 73 68 |iles,.# |type "sh|
|000002d0| 20 66 69 6c 65 20 2d 63 | 22 2e 0a 23 20 43 6f 6e | file -c|"..# Con|
|000002e0| 74 65 6e 74 73 3a 20 20 | 6a 71 75 61 6e 74 32 2e |tents: |jquant2.|
|000002f0| 63 20 6a 72 64 70 70 6d | 2e 63 0a 23 20 57 72 61 |c jrdppm|.c.# Wra|
|00000300| 70 70 65 64 20 62 79 20 | 6b 65 6e 74 40 73 70 61 |pped by |kent@spa|
|00000310| 72 6b 79 20 6f 6e 20 57 | 65 64 20 44 65 63 20 31 |rky on W|ed Dec 1|
|00000320| 36 20 32 30 3a 35 32 3a | 32 34 20 31 39 39 32 0a |6 20:52:|24 1992.|
|00000330| 50 41 54 48 3d 2f 62 69 | 6e 3a 2f 75 73 72 2f 62 |PATH=/bi|n:/usr/b|
|00000340| 69 6e 3a 2f 75 73 72 2f | 75 63 62 3a 2f 75 73 72 |in:/usr/|ucb:/usr|
|00000350| 2f 6c 6f 63 61 6c 2f 62 | 69 6e 3a 2f 75 73 72 2f |/local/b|in:/usr/|
|00000360| 6c 62 69 6e 20 3b 20 65 | 78 70 6f 72 74 20 50 41 |lbin ; e|xport PA|
|00000370| 54 48 0a 65 63 68 6f 20 | 49 66 20 74 68 69 73 20 |TH.echo |If this |
|00000380| 61 72 63 68 69 76 65 20 | 69 73 20 63 6f 6d 70 6c |archive |is compl|
|00000390| 65 74 65 2c 20 79 6f 75 | 20 77 69 6c 6c 20 73 65 |ete, you| will se|
|000003a0| 65 20 74 68 65 20 66 6f | 6c 6c 6f 77 69 6e 67 20 |e the fo|llowing |
|000003b0| 6d 65 73 73 61 67 65 3a | 0a 65 63 68 6f 20 27 20 |message:|.echo ' |
|000003c0| 20 20 20 20 20 20 20 20 | 20 22 73 68 61 72 3a 20 | | "shar: |
|000003d0| 45 6e 64 20 6f 66 20 61 | 72 63 68 69 76 65 20 32 |End of a|rchive 2|
|000003e0| 20 28 6f 66 20 31 38 29 | 2e 22 27 0a 69 66 20 74 | (of 18)|."'.if t|
|000003f0| 65 73 74 20 2d 66 20 27 | 6a 71 75 61 6e 74 32 2e |est -f '|jquant2.|
|00000400| 63 27 20 2d 61 20 22 24 | 7b 31 7d 22 20 21 3d 20 |c' -a "$|{1}" != |
|00000410| 22 2d 63 22 20 3b 20 74 | 68 65 6e 20 0a 20 20 65 |"-c" ; t|hen . e|
|00000420| 63 68 6f 20 73 68 61 72 | 3a 20 57 69 6c 6c 20 6e |cho shar|: Will n|
|00000430| 6f 74 20 63 6c 6f 62 62 | 65 72 20 65 78 69 73 74 |ot clobb|er exist|
|00000440| 69 6e 67 20 66 69 6c 65 | 20 5c 22 27 6a 71 75 61 |ing file| \"'jqua|
|00000450| 6e 74 32 2e 63 27 5c 22 | 0a 65 6c 73 65 0a 20 20 |nt2.c'\"|.else. |
|00000460| 65 63 68 6f 20 73 68 61 | 72 3a 20 45 78 74 72 61 |echo sha|r: Extra|
|00000470| 63 74 69 6e 67 20 5c 22 | 27 6a 71 75 61 6e 74 32 |cting \"|'jquant2|
|00000480| 2e 63 27 5c 22 20 5c 28 | 34 32 31 39 34 20 63 68 |.c'\" \(|42194 ch|
|00000490| 61 72 61 63 74 65 72 73 | 5c 29 0a 20 20 73 65 64 |aracters|\). sed|
|000004a0| 20 22 73 2f 5e 58 2f 2f | 22 20 3e 27 6a 71 75 61 | "s/^X//|" >'jqua|
|000004b0| 6e 74 32 2e 63 27 20 3c | 3c 27 45 4e 44 5f 4f 46 |nt2.c' <|<'END_OF|
|000004c0| 5f 46 49 4c 45 27 0a 58 | 2f 2a 0a 58 20 2a 20 6a |_FILE'.X|/*.X * j|
|000004d0| 71 75 61 6e 74 32 2e 63 | 0a 58 20 2a 0a 58 20 2a |quant2.c|.X *.X *|
|000004e0| 20 43 6f 70 79 72 69 67 | 68 74 20 28 43 29 20 31 | Copyrig|ht (C) 1|
|000004f0| 39 39 31 2c 20 31 39 39 | 32 2c 20 54 68 6f 6d 61 |991, 199|2, Thoma|
|00000500| 73 20 47 2e 20 4c 61 6e | 65 2e 0a 58 20 2a 20 54 |s G. Lan|e..X * T|
|00000510| 68 69 73 20 66 69 6c 65 | 20 69 73 20 70 61 72 74 |his file| is part|
|00000520| 20 6f 66 20 74 68 65 20 | 49 6e 64 65 70 65 6e 64 | of the |Independ|
|00000530| 65 6e 74 20 4a 50 45 47 | 20 47 72 6f 75 70 27 73 |ent JPEG| Group's|
|00000540| 20 73 6f 66 74 77 61 72 | 65 2e 0a 58 20 2a 20 46 | softwar|e..X * F|
|00000550| 6f 72 20 63 6f 6e 64 69 | 74 69 6f 6e 73 20 6f 66 |or condi|tions of|
|00000560| 20 64 69 73 74 72 69 62 | 75 74 69 6f 6e 20 61 6e | distrib|ution an|
|00000570| 64 20 75 73 65 2c 20 73 | 65 65 20 74 68 65 20 61 |d use, s|ee the a|
|00000580| 63 63 6f 6d 70 61 6e 79 | 69 6e 67 20 52 45 41 44 |ccompany|ing READ|
|00000590| 4d 45 20 66 69 6c 65 2e | 0a 58 20 2a 0a 58 20 2a |ME file.|.X *.X *|
|000005a0| 20 54 68 69 73 20 66 69 | 6c 65 20 63 6f 6e 74 61 | This fi|le conta|
|000005b0| 69 6e 73 20 32 2d 70 61 | 73 73 20 63 6f 6c 6f 72 |ins 2-pa|ss color|
|000005c0| 20 71 75 61 6e 74 69 7a | 61 74 69 6f 6e 20 28 63 | quantiz|ation (c|
|000005d0| 6f 6c 6f 72 20 6d 61 70 | 70 69 6e 67 29 20 72 6f |olor map|ping) ro|
|000005e0| 75 74 69 6e 65 73 2e 0a | 58 20 2a 20 54 68 65 73 |utines..|X * Thes|
|000005f0| 65 20 72 6f 75 74 69 6e | 65 73 20 61 72 65 20 69 |e routin|es are i|
|00000600| 6e 76 6f 6b 65 64 20 76 | 69 61 20 74 68 65 20 6d |nvoked v|ia the m|
|00000610| 65 74 68 6f 64 73 20 63 | 6f 6c 6f 72 5f 71 75 61 |ethods c|olor_qua|
|00000620| 6e 74 5f 70 72 65 73 63 | 61 6e 2c 0a 58 20 2a 20 |nt_presc|an,.X * |
|00000630| 63 6f 6c 6f 72 5f 71 75 | 61 6e 74 5f 64 6f 69 74 |color_qu|ant_doit|
|00000640| 2c 20 61 6e 64 20 63 6f | 6c 6f 72 5f 71 75 61 6e |, and co|lor_quan|
|00000650| 74 5f 69 6e 69 74 2f 74 | 65 72 6d 2e 0a 58 20 2a |t_init/t|erm..X *|
|00000660| 2f 0a 58 0a 58 23 69 6e | 63 6c 75 64 65 20 22 6a |/.X.X#in|clude "j|
|00000670| 69 6e 63 6c 75 64 65 2e | 68 22 0a 58 0a 58 23 69 |include.|h".X.X#i|
|00000680| 66 64 65 66 20 51 55 41 | 4e 54 5f 32 50 41 53 53 |fdef QUA|NT_2PASS|
|00000690| 5f 53 55 50 50 4f 52 54 | 45 44 0a 58 0a 58 0a 58 |_SUPPORT|ED.X.X.X|
|000006a0| 2f 2a 0a 58 20 2a 20 54 | 68 69 73 20 6d 6f 64 75 |/*.X * T|his modu|
|000006b0| 6c 65 20 69 6d 70 6c 65 | 6d 65 6e 74 73 20 74 68 |le imple|ments th|
|000006c0| 65 20 77 65 6c 6c 2d 6b | 6e 6f 77 6e 20 48 65 63 |e well-k|nown Hec|
|000006d0| 6b 62 65 72 74 20 70 61 | 72 61 64 69 67 6d 20 66 |kbert pa|radigm f|
|000006e0| 6f 72 20 63 6f 6c 6f 72 | 0a 58 20 2a 20 71 75 61 |or color|.X * qua|
|000006f0| 6e 74 69 7a 61 74 69 6f | 6e 2e 20 20 4d 6f 73 74 |ntizatio|n. Most|
|00000700| 20 6f 66 20 74 68 65 20 | 69 64 65 61 73 20 75 73 | of the |ideas us|
|00000710| 65 64 20 68 65 72 65 20 | 63 61 6e 20 62 65 20 74 |ed here |can be t|
|00000720| 72 61 63 65 64 20 62 61 | 63 6b 20 74 6f 0a 58 20 |raced ba|ck to.X |
|00000730| 2a 20 48 65 63 6b 62 65 | 72 74 27 73 20 73 65 6d |* Heckbe|rt's sem|
|00000740| 69 6e 61 6c 20 70 61 70 | 65 72 0a 58 20 2a 20 20 |inal pap|er.X * |
|00000750| 20 48 65 63 6b 62 65 72 | 74 2c 20 50 61 75 6c 2e | Heckber|t, Paul.|
|00000760| 20 20 22 43 6f 6c 6f 72 | 20 49 6d 61 67 65 20 51 | "Color| Image Q|
|00000770| 75 61 6e 74 69 7a 61 74 | 69 6f 6e 20 66 6f 72 20 |uantizat|ion for |
|00000780| 46 72 61 6d 65 20 42 75 | 66 66 65 72 20 44 69 73 |Frame Bu|ffer Dis|
|00000790| 70 6c 61 79 22 2c 0a 58 | 20 2a 20 20 20 50 72 6f |play",.X| * Pro|
|000007a0| 63 2e 20 53 49 47 47 52 | 41 50 48 20 27 38 32 2c |c. SIGGR|APH '82,|
|000007b0| 20 43 6f 6d 70 75 74 65 | 72 20 47 72 61 70 68 69 | Compute|r Graphi|
|000007c0| 63 73 20 76 2e 31 36 20 | 23 33 20 28 4a 75 6c 79 |cs v.16 |#3 (July|
|000007d0| 20 31 39 38 32 29 2c 20 | 70 70 20 32 39 37 2d 33 | 1982), |pp 297-3|
|000007e0| 30 34 2e 0a 58 20 2a 0a | 58 20 2a 20 49 6e 20 74 |04..X *.|X * In t|
|000007f0| 68 65 20 66 69 72 73 74 | 20 70 61 73 73 20 6f 76 |he first| pass ov|
|00000800| 65 72 20 74 68 65 20 69 | 6d 61 67 65 2c 20 77 65 |er the i|mage, we|
|00000810| 20 61 63 63 75 6d 75 6c | 61 74 65 20 61 20 68 69 | accumul|ate a hi|
|00000820| 73 74 6f 67 72 61 6d 20 | 73 68 6f 77 69 6e 67 20 |stogram |showing |
|00000830| 74 68 65 0a 58 20 2a 20 | 75 73 61 67 65 20 63 6f |the.X * |usage co|
|00000840| 75 6e 74 20 6f 66 20 65 | 61 63 68 20 70 6f 73 73 |unt of e|ach poss|
|00000850| 69 62 6c 65 20 63 6f 6c | 6f 72 2e 20 20 28 54 6f |ible col|or. (To|
|00000860| 20 6b 65 65 70 20 74 68 | 65 20 68 69 73 74 6f 67 | keep th|e histog|
|00000870| 72 61 6d 20 74 6f 20 61 | 20 72 65 61 73 6f 6e 61 |ram to a| reasona|
|00000880| 62 6c 65 0a 58 20 2a 20 | 73 69 7a 65 2c 20 77 65 |ble.X * |size, we|
|00000890| 20 72 65 64 75 63 65 20 | 74 68 65 20 70 72 65 63 | reduce |the prec|
|000008a0| 69 73 69 6f 6e 20 6f 66 | 20 74 68 65 20 69 6e 70 |ision of| the inp|
|000008b0| 75 74 3b 20 74 79 70 69 | 63 61 6c 20 70 72 61 63 |ut; typi|cal prac|
|000008c0| 74 69 63 65 20 69 73 20 | 74 6f 20 72 65 74 61 69 |tice is |to retai|
|000008d0| 6e 0a 58 20 2a 20 35 20 | 6f 72 20 36 20 62 69 74 |n.X * 5 |or 6 bit|
|000008e0| 73 20 70 65 72 20 63 6f | 6c 6f 72 2c 20 73 6f 20 |s per co|lor, so |
|000008f0| 74 68 61 74 20 38 20 6f | 72 20 34 20 64 69 66 66 |that 8 o|r 4 diff|
|00000900| 65 72 65 6e 74 20 69 6e | 70 75 74 20 76 61 6c 75 |erent in|put valu|
|00000910| 65 73 20 61 72 65 20 63 | 6f 75 6e 74 65 64 0a 58 |es are c|ounted.X|
|00000920| 20 2a 20 69 6e 20 74 68 | 65 20 73 61 6d 65 20 68 | * in th|e same h|
|00000930| 69 73 74 6f 67 72 61 6d | 20 63 65 6c 6c 2e 29 20 |istogram| cell.) |
|00000940| 20 4e 65 78 74 2c 20 74 | 68 65 20 63 6f 6c 6f 72 | Next, t|he color|
|00000950| 2d 73 65 6c 65 63 74 69 | 6f 6e 20 73 74 65 70 20 |-selecti|on step |
|00000960| 62 65 67 69 6e 73 20 77 | 69 74 68 20 61 0a 58 20 |begins w|ith a.X |
|00000970| 2a 20 62 6f 78 20 72 65 | 70 72 65 73 65 6e 74 69 |* box re|presenti|
|00000980| 6e 67 20 74 68 65 20 77 | 68 6f 6c 65 20 63 6f 6c |ng the w|hole col|
|00000990| 6f 72 20 73 70 61 63 65 | 2c 20 61 6e 64 20 72 65 |or space|, and re|
|000009a0| 70 65 61 74 65 64 6c 79 | 20 73 70 6c 69 74 73 20 |peatedly| splits |
|000009b0| 74 68 65 20 22 6c 61 72 | 67 65 73 74 22 0a 58 20 |the "lar|gest".X |
|000009c0| 2a 20 72 65 6d 61 69 6e | 69 6e 67 20 62 6f 78 20 |* remain|ing box |
|000009d0| 75 6e 74 69 6c 20 77 65 | 20 68 61 76 65 20 61 73 |until we| have as|
|000009e0| 20 6d 61 6e 79 20 62 6f | 78 65 73 20 61 73 20 64 | many bo|xes as d|
|000009f0| 65 73 69 72 65 64 20 63 | 6f 6c 6f 72 73 2e 20 20 |esired c|olors. |
|00000a00| 54 68 65 6e 20 74 68 65 | 20 6d 65 61 6e 0a 58 20 |Then the| mean.X |
|00000a10| 2a 20 63 6f 6c 6f 72 20 | 69 6e 20 65 61 63 68 20 |* color |in each |
|00000a20| 72 65 6d 61 69 6e 69 6e | 67 20 62 6f 78 20 62 65 |remainin|g box be|
|00000a30| 63 6f 6d 65 73 20 6f 6e | 65 20 6f 66 20 74 68 65 |comes on|e of the|
|00000a40| 20 70 6f 73 73 69 62 6c | 65 20 6f 75 74 70 75 74 | possibl|e output|
|00000a50| 20 63 6f 6c 6f 72 73 2e | 0a 58 20 2a 20 54 68 65 | colors.|.X * The|
|00000a60| 20 73 65 63 6f 6e 64 20 | 70 61 73 73 20 6f 76 65 | second |pass ove|
|00000a70| 72 20 74 68 65 20 69 6d | 61 67 65 20 6d 61 70 73 |r the im|age maps|
|00000a80| 20 65 61 63 68 20 69 6e | 70 75 74 20 70 69 78 65 | each in|put pixe|
|00000a90| 6c 20 74 6f 20 74 68 65 | 20 63 6c 6f 73 65 73 74 |l to the| closest|
|00000aa0| 20 6f 75 74 70 75 74 0a | 58 20 2a 20 63 6f 6c 6f | output.|X * colo|
|00000ab0| 72 20 28 6f 70 74 69 6f | 6e 61 6c 6c 79 20 61 66 |r (optio|nally af|
|00000ac0| 74 65 72 20 61 70 70 6c | 79 69 6e 67 20 61 20 46 |ter appl|ying a F|
|00000ad0| 6c 6f 79 64 2d 53 74 65 | 69 6e 62 65 72 67 20 64 |loyd-Ste|inberg d|
|00000ae0| 69 74 68 65 72 69 6e 67 | 20 63 6f 72 72 65 63 74 |ithering| correct|
|00000af0| 69 6f 6e 29 2e 0a 58 20 | 2a 20 54 68 69 73 20 6d |ion)..X |* This m|
|00000b00| 61 70 70 69 6e 67 20 69 | 73 20 6c 6f 67 69 63 61 |apping i|s logica|
|00000b10| 6c 6c 79 20 74 72 69 76 | 69 61 6c 2c 20 62 75 74 |lly triv|ial, but|
|00000b20| 20 6d 61 6b 69 6e 67 20 | 69 74 20 67 6f 20 66 61 | making |it go fa|
|00000b30| 73 74 20 65 6e 6f 75 67 | 68 20 72 65 71 75 69 72 |st enoug|h requir|
|00000b40| 65 73 0a 58 20 2a 20 63 | 6f 6e 73 69 64 65 72 61 |es.X * c|onsidera|
|00000b50| 62 6c 65 20 63 61 72 65 | 2e 0a 58 20 2a 0a 58 20 |ble care|..X *.X |
|00000b60| 2a 20 48 65 63 6b 62 65 | 72 74 2d 73 74 79 6c 65 |* Heckbe|rt-style|
|00000b70| 20 71 75 61 6e 74 69 7a | 65 72 73 20 76 61 72 79 | quantiz|ers vary|
|00000b80| 20 61 20 67 6f 6f 64 20 | 64 65 61 6c 20 69 6e 20 | a good |deal in |
|00000b90| 74 68 65 69 72 20 70 6f | 6c 69 63 69 65 73 20 66 |their po|licies f|
|00000ba0| 6f 72 20 63 68 6f 6f 73 | 69 6e 67 0a 58 20 2a 20 |or choos|ing.X * |
|00000bb0| 74 68 65 20 22 6c 61 72 | 67 65 73 74 22 20 62 6f |the "lar|gest" bo|
|00000bc0| 78 20 61 6e 64 20 64 65 | 63 69 64 69 6e 67 20 77 |x and de|ciding w|
|00000bd0| 68 65 72 65 20 74 6f 20 | 63 75 74 20 69 74 2e 20 |here to |cut it. |
|00000be0| 20 54 68 65 20 70 61 72 | 74 69 63 75 6c 61 72 20 | The par|ticular |
|00000bf0| 70 6f 6c 69 63 69 65 73 | 0a 58 20 2a 20 75 73 65 |policies|.X * use|
|00000c00| 64 20 68 65 72 65 20 68 | 61 76 65 20 70 72 6f 76 |d here h|ave prov|
|00000c10| 65 64 20 6f 75 74 20 77 | 65 6c 6c 20 69 6e 20 65 |ed out w|ell in e|
|00000c20| 78 70 65 72 69 6d 65 6e | 74 61 6c 20 63 6f 6d 70 |xperimen|tal comp|
|00000c30| 61 72 69 73 6f 6e 73 2c | 20 62 75 74 20 62 65 74 |arisons,| but bet|
|00000c40| 74 65 72 20 6f 6e 65 73 | 0a 58 20 2a 20 6d 61 79 |ter ones|.X * may|
|00000c50| 20 79 65 74 20 62 65 20 | 66 6f 75 6e 64 2e 0a 58 | yet be |found..X|
|00000c60| 20 2a 0a 58 20 2a 20 54 | 68 65 20 6d 6f 73 74 20 | *.X * T|he most |
|00000c70| 73 69 67 6e 69 66 69 63 | 61 6e 74 20 64 69 66 66 |signific|ant diff|
|00000c80| 65 72 65 6e 63 65 20 62 | 65 74 77 65 65 6e 20 74 |erence b|etween t|
|00000c90| 68 69 73 20 71 75 61 6e | 74 69 7a 65 72 20 61 6e |his quan|tizer an|
|00000ca0| 64 20 6f 74 68 65 72 73 | 20 69 73 20 74 68 61 74 |d others| is that|
|00000cb0| 0a 58 20 2a 20 74 68 69 | 73 20 6f 6e 65 20 69 73 |.X * thi|s one is|
|00000cc0| 20 69 6e 74 65 6e 64 65 | 64 20 74 6f 20 6f 70 65 | intende|d to ope|
|00000cd0| 72 61 74 65 20 69 6e 20 | 59 43 62 43 72 20 63 6f |rate in |YCbCr co|
|00000ce0| 6c 6f 72 73 70 61 63 65 | 2c 20 72 61 74 68 65 72 |lorspace|, rather|
|00000cf0| 20 74 68 61 6e 20 52 47 | 42 20 73 70 61 63 65 0a | than RG|B space.|
|00000d00| 58 20 2a 20 61 73 20 69 | 73 20 75 73 75 61 6c 6c |X * as i|s usuall|
|00000d10| 79 20 64 6f 6e 65 2e 20 | 20 41 63 74 75 61 6c 6c |y done. | Actuall|
|00000d20| 79 20 77 65 20 77 6f 72 | 6b 20 69 6e 20 73 63 61 |y we wor|k in sca|
|00000d30| 6c 65 64 20 59 43 62 43 | 72 20 63 6f 6c 6f 72 73 |led YCbC|r colors|
|00000d40| 70 61 63 65 2c 20 77 68 | 65 72 65 0a 58 20 2a 20 |pace, wh|ere.X * |
|00000d50| 59 20 64 69 73 74 61 6e | 63 65 73 20 61 72 65 20 |Y distan|ces are |
|00000d60| 69 6e 66 6c 61 74 65 64 | 20 62 79 20 61 20 66 61 |inflated| by a fa|
|00000d70| 63 74 6f 72 20 6f 66 20 | 32 20 72 65 6c 61 74 69 |ctor of |2 relati|
|00000d80| 76 65 20 74 6f 20 43 62 | 20 6f 72 20 43 72 20 64 |ve to Cb| or Cr d|
|00000d90| 69 73 74 61 6e 63 65 73 | 2e 0a 58 20 2a 20 54 68 |istances|..X * Th|
|00000da0| 65 20 65 6d 70 69 72 69 | 63 61 6c 20 65 76 69 64 |e empiri|cal evid|
|00000db0| 65 6e 63 65 20 69 73 20 | 74 68 61 74 20 64 69 73 |ence is |that dis|
|00000dc0| 74 61 6e 63 65 73 20 69 | 6e 20 74 68 69 73 20 73 |tances i|n this s|
|00000dd0| 70 61 63 65 20 63 6f 72 | 72 65 73 70 6f 6e 64 20 |pace cor|respond |
|00000de0| 74 6f 0a 58 20 2a 20 70 | 65 72 63 65 70 74 75 61 |to.X * p|erceptua|
|00000df0| 6c 20 63 6f 6c 6f 72 20 | 64 69 66 66 65 72 65 6e |l color |differen|
|00000e00| 63 65 73 20 6d 6f 72 65 | 20 63 6c 6f 73 65 6c 79 |ces more| closely|
|00000e10| 20 74 68 61 6e 20 64 6f | 20 64 69 73 74 61 6e 63 | than do| distanc|
|00000e20| 65 73 20 69 6e 20 52 47 | 42 20 73 70 61 63 65 3b |es in RG|B space;|
|00000e30| 0a 58 20 2a 20 61 6e 64 | 20 77 6f 72 6b 69 6e 67 |.X * and| working|
|00000e40| 20 69 6e 20 74 68 69 73 | 20 73 70 61 63 65 20 69 | in this| space i|
|00000e50| 73 20 69 6e 65 78 70 65 | 6e 73 69 76 65 20 77 69 |s inexpe|nsive wi|
|00000e60| 74 68 69 6e 20 61 20 4a | 50 45 47 20 64 65 63 6f |thin a J|PEG deco|
|00000e70| 6d 70 72 65 73 73 6f 72 | 2c 20 73 69 6e 63 65 0a |mpressor|, since.|
|00000e80| 58 20 2a 20 74 68 65 20 | 69 6e 70 75 74 20 64 61 |X * the |input da|
|00000e90| 74 61 20 69 73 20 61 6c | 72 65 61 64 79 20 69 6e |ta is al|ready in|
|00000ea0| 20 59 43 62 43 72 20 66 | 6f 72 6d 2e 20 20 28 57 | YCbCr f|orm. (W|
|00000eb0| 65 20 63 6f 75 6c 64 20 | 74 72 61 6e 73 66 6f 72 |e could |transfor|
|00000ec0| 6d 20 74 6f 20 61 6e 20 | 65 76 65 6e 0a 58 20 2a |m to an |even.X *|
|00000ed0| 20 6d 6f 72 65 20 70 65 | 72 63 65 70 74 75 61 6c | more pe|rceptual|
|00000ee0| 6c 79 20 6c 69 6e 65 61 | 72 20 73 70 61 63 65 20 |ly linea|r space |
|00000ef0| 73 75 63 68 20 61 73 20 | 4c 61 62 20 6f 72 20 4c |such as |Lab or L|
|00000f00| 75 76 2c 20 62 75 74 20 | 74 68 61 74 20 69 73 20 |uv, but |that is |
|00000f10| 76 65 72 79 20 73 6c 6f | 77 0a 58 20 2a 20 61 6e |very slo|w.X * an|
|00000f20| 64 20 64 6f 65 73 6e 27 | 74 20 79 69 65 6c 64 20 |d doesn'|t yield |
|00000f30| 6d 75 63 68 20 62 65 74 | 74 65 72 20 72 65 73 75 |much bet|ter resu|
|00000f40| 6c 74 73 20 74 68 61 6e | 20 73 63 61 6c 65 64 20 |lts than| scaled |
|00000f50| 59 43 62 43 72 2e 29 0a | 58 20 2a 2f 0a 58 0a 58 |YCbCr.).|X */.X.X|
|00000f60| 23 64 65 66 69 6e 65 20 | 59 5f 53 43 41 4c 45 20 |#define |Y_SCALE |
|00000f70| 32 09 09 2f 2a 20 73 63 | 61 6c 65 20 59 20 64 69 |2../* sc|ale Y di|
|00000f80| 73 74 61 6e 63 65 73 20 | 75 70 20 62 79 20 74 68 |stances |up by th|
|00000f90| 69 73 20 6d 75 63 68 20 | 2a 2f 0a 58 0a 58 23 64 |is much |*/.X.X#d|
|00000fa0| 65 66 69 6e 65 20 4d 41 | 58 4e 55 4d 43 4f 4c 4f |efine MA|XNUMCOLO|
|00000fb0| 52 53 20 20 28 4d 41 58 | 4a 53 41 4d 50 4c 45 2b |RS (MAX|JSAMPLE+|
|00000fc0| 31 29 20 2f 2a 20 6d 61 | 78 69 6d 75 6d 20 73 69 |1) /* ma|ximum si|
|00000fd0| 7a 65 20 6f 66 20 63 6f | 6c 6f 72 6d 61 70 20 2a |ze of co|lormap *|
|00000fe0| 2f 0a 58 0a 58 0a 58 2f | 2a 0a 58 20 2a 20 46 69 |/.X.X.X/|*.X * Fi|
|00000ff0| 72 73 74 20 77 65 20 68 | 61 76 65 20 74 68 65 20 |rst we h|ave the |
|00001000| 68 69 73 74 6f 67 72 61 | 6d 20 64 61 74 61 20 73 |histogra|m data s|
|00001010| 74 72 75 63 74 75 72 65 | 20 61 6e 64 20 72 6f 75 |tructure| and rou|
|00001020| 74 69 6e 65 73 20 66 6f | 72 20 63 72 65 61 74 69 |tines fo|r creati|
|00001030| 6e 67 20 69 74 2e 0a 58 | 20 2a 0a 58 20 2a 20 46 |ng it..X| *.X * F|
|00001040| 6f 72 20 77 6f 72 6b 20 | 69 6e 20 59 43 62 43 72 |or work |in YCbCr|
|00001050| 20 73 70 61 63 65 2c 20 | 69 74 20 69 73 20 75 73 | space, |it is us|
|00001060| 65 66 75 6c 20 74 6f 20 | 6b 65 65 70 20 6d 6f 72 |eful to |keep mor|
|00001070| 65 20 70 72 65 63 69 73 | 69 6f 6e 20 66 6f 72 20 |e precis|ion for |
|00001080| 59 20 74 68 61 6e 0a 58 | 20 2a 20 66 6f 72 20 43 |Y than.X| * for C|
|00001090| 62 20 6f 72 20 43 72 2e | 20 20 57 65 20 72 65 63 |b or Cr.| We rec|
|000010a0| 6f 6d 6d 65 6e 64 20 6b | 65 65 70 69 6e 67 20 36 |ommend k|eeping 6|
|000010b0| 20 62 69 74 73 20 66 6f | 72 20 59 20 61 6e 64 20 | bits fo|r Y and |
|000010c0| 35 20 62 69 74 73 20 65 | 61 63 68 20 66 6f 72 20 |5 bits e|ach for |
|000010d0| 43 62 2f 43 72 2e 0a 58 | 20 2a 20 49 66 20 79 6f |Cb/Cr..X| * If yo|
|000010e0| 75 20 68 61 76 65 20 70 | 6c 65 6e 74 79 20 6f 66 |u have p|lenty of|
|000010f0| 20 6d 65 6d 6f 72 79 20 | 61 6e 64 20 63 79 63 6c | memory |and cycl|
|00001100| 65 73 2c 20 36 20 62 69 | 74 73 20 61 6c 6c 20 61 |es, 6 bi|ts all a|
|00001110| 72 6f 75 6e 64 20 67 69 | 76 65 73 20 6d 61 72 67 |round gi|ves marg|
|00001120| 69 6e 61 6c 6c 79 0a 58 | 20 2a 20 62 65 74 74 65 |inally.X| * bette|
|00001130| 72 20 72 65 73 75 6c 74 | 73 3b 20 69 66 20 79 6f |r result|s; if yo|
|00001140| 75 20 61 72 65 20 73 68 | 6f 72 74 20 6f 66 20 6d |u are sh|ort of m|
|00001150| 65 6d 6f 72 79 2c 20 35 | 20 62 69 74 73 20 61 6c |emory, 5| bits al|
|00001160| 6c 20 61 72 6f 75 6e 64 | 20 77 69 6c 6c 20 73 61 |l around| will sa|
|00001170| 76 65 0a 58 20 2a 20 73 | 6f 6d 65 20 73 70 61 63 |ve.X * s|ome spac|
|00001180| 65 20 62 75 74 20 64 65 | 67 72 61 64 65 20 74 68 |e but de|grade th|
|00001190| 65 20 72 65 73 75 6c 74 | 73 2e 0a 58 20 2a 20 54 |e result|s..X * T|
|000011a0| 6f 20 6d 61 69 6e 74 61 | 69 6e 20 61 20 66 75 6c |o mainta|in a ful|
|000011b0| 6c 79 20 61 63 63 75 72 | 61 74 65 20 68 69 73 74 |ly accur|ate hist|
|000011c0| 6f 67 72 61 6d 2c 20 77 | 65 27 64 20 6e 65 65 64 |ogram, w|e'd need|
|000011d0| 20 74 6f 20 61 6c 6c 6f | 63 61 74 65 20 61 20 22 | to allo|cate a "|
|000011e0| 6c 6f 6e 67 22 0a 58 20 | 2a 20 28 70 72 65 66 65 |long".X |* (prefe|
|000011f0| 72 61 62 6c 79 20 75 6e | 73 69 67 6e 65 64 20 6c |rably un|signed l|
|00001200| 6f 6e 67 29 20 66 6f 72 | 20 65 61 63 68 20 63 65 |ong) for| each ce|
|00001210| 6c 6c 2e 20 20 49 6e 20 | 70 72 61 63 74 69 63 65 |ll. In |practice|
|00001220| 20 74 68 69 73 20 69 73 | 20 6f 76 65 72 6b 69 6c | this is| overkil|
|00001230| 6c 3b 0a 58 20 2a 20 77 | 65 20 63 61 6e 20 67 65 |l;.X * w|e can ge|
|00001240| 74 20 62 79 20 77 69 74 | 68 20 31 36 20 62 69 74 |t by wit|h 16 bit|
|00001250| 73 20 70 65 72 20 63 65 | 6c 6c 2e 20 20 46 65 77 |s per ce|ll. Few|
|00001260| 20 6f 66 20 74 68 65 20 | 63 65 6c 6c 20 63 6f 75 | of the |cell cou|
|00001270| 6e 74 73 20 77 69 6c 6c | 20 6f 76 65 72 66 6c 6f |nts will| overflo|
|00001280| 77 2c 0a 58 20 2a 20 61 | 6e 64 20 63 6c 61 6d 70 |w,.X * a|nd clamp|
|00001290| 69 6e 67 20 74 68 6f 73 | 65 20 74 68 61 74 20 64 |ing thos|e that d|
|000012a0| 6f 20 6f 76 65 72 66 6c | 6f 77 20 74 6f 20 74 68 |o overfl|ow to th|
|000012b0| 65 20 6d 61 78 69 6d 75 | 6d 20 76 61 6c 75 65 20 |e maximu|m value |
|000012c0| 77 69 6c 6c 20 67 69 76 | 65 20 63 6c 6f 73 65 2d |will giv|e close-|
|000012d0| 0a 58 20 2a 20 65 6e 6f | 75 67 68 20 72 65 73 75 |.X * eno|ugh resu|
|000012e0| 6c 74 73 2e 20 20 54 68 | 69 73 20 72 65 64 75 63 |lts. Th|is reduc|
|000012f0| 65 73 20 74 68 65 20 72 | 65 63 6f 6d 6d 65 6e 64 |es the r|ecommend|
|00001300| 65 64 20 68 69 73 74 6f | 67 72 61 6d 20 73 69 7a |ed histo|gram siz|
|00001310| 65 20 66 72 6f 6d 20 32 | 35 36 4b 62 0a 58 20 2a |e from 2|56Kb.X *|
|00001320| 20 74 6f 20 31 32 38 4b | 62 2c 20 77 68 69 63 68 | to 128K|b, which|
|00001330| 20 69 73 20 61 20 75 73 | 65 66 75 6c 20 73 61 76 | is a us|eful sav|
|00001340| 69 6e 67 73 20 6f 6e 20 | 50 43 2d 63 6c 61 73 73 |ings on |PC-class|
|00001350| 20 6d 61 63 68 69 6e 65 | 73 2e 0a 58 20 2a 20 28 | machine|s..X * (|
|00001360| 49 6e 20 74 68 65 20 73 | 65 63 6f 6e 64 20 70 61 |In the s|econd pa|
|00001370| 73 73 20 74 68 65 20 68 | 69 73 74 6f 67 72 61 6d |ss the h|istogram|
|00001380| 20 73 70 61 63 65 20 69 | 73 20 72 65 2d 75 73 65 | space i|s re-use|
|00001390| 64 20 66 6f 72 20 70 69 | 78 65 6c 20 6d 61 70 70 |d for pi|xel mapp|
|000013a0| 69 6e 67 20 64 61 74 61 | 3b 0a 58 20 2a 20 69 6e |ing data|;.X * in|
|000013b0| 20 74 68 61 74 20 63 61 | 70 61 63 69 74 79 2c 20 | that ca|pacity, |
|000013c0| 65 61 63 68 20 63 65 6c | 6c 20 6d 75 73 74 20 62 |each cel|l must b|
|000013d0| 65 20 61 62 6c 65 20 74 | 6f 20 73 74 6f 72 65 20 |e able t|o store |
|000013e0| 7a 65 72 6f 20 74 6f 20 | 74 68 65 20 6e 75 6d 62 |zero to |the numb|
|000013f0| 65 72 20 6f 66 0a 58 20 | 2a 20 64 65 73 69 72 65 |er of.X |* desire|
|00001400| 64 20 63 6f 6c 6f 72 73 | 2e 20 20 31 36 20 62 69 |d colors|. 16 bi|
|00001410| 74 73 2f 63 65 6c 6c 20 | 69 73 20 70 6c 65 6e 74 |ts/cell |is plent|
|00001420| 79 20 66 6f 72 20 74 68 | 61 74 20 74 6f 6f 2e 29 |y for th|at too.)|
|00001430| 0a 58 20 2a 20 53 69 6e | 63 65 20 74 68 65 20 4a |.X * Sin|ce the J|
|00001440| 50 45 47 20 63 6f 64 65 | 20 69 73 20 69 6e 74 65 |PEG code| is inte|
|00001450| 6e 64 65 64 20 74 6f 20 | 72 75 6e 20 69 6e 20 73 |nded to |run in s|
|00001460| 6d 61 6c 6c 20 6d 65 6d | 6f 72 79 20 6d 6f 64 65 |mall mem|ory mode|
|00001470| 6c 20 6f 6e 20 38 30 78 | 38 36 0a 58 20 2a 20 6d |l on 80x|86.X * m|
|00001480| 61 63 68 69 6e 65 73 2c | 20 77 65 20 63 61 6e 27 |achines,| we can'|
|00001490| 74 20 6a 75 73 74 20 61 | 6c 6c 6f 63 61 74 65 20 |t just a|llocate |
|000014a0| 74 68 65 20 68 69 73 74 | 6f 67 72 61 6d 20 69 6e |the hist|ogram in|
|000014b0| 20 6f 6e 65 20 63 68 75 | 6e 6b 2e 20 20 49 6e 73 | one chu|nk. Ins|
|000014c0| 74 65 61 64 0a 58 20 2a | 20 6f 66 20 61 20 74 72 |tead.X *| of a tr|
|000014d0| 75 65 20 33 2d 44 20 61 | 72 72 61 79 2c 20 77 65 |ue 3-D a|rray, we|
|000014e0| 20 75 73 65 20 61 20 72 | 6f 77 20 6f 66 20 70 6f | use a r|ow of po|
|000014f0| 69 6e 74 65 72 73 20 74 | 6f 20 32 2d 44 20 61 72 |inters t|o 2-D ar|
|00001500| 72 61 79 73 2e 20 20 45 | 61 63 68 0a 58 20 2a 20 |rays. E|ach.X * |
|00001510| 70 6f 69 6e 74 65 72 20 | 63 6f 72 72 65 73 70 6f |pointer |correspo|
|00001520| 6e 64 73 20 74 6f 20 61 | 20 59 20 76 61 6c 75 65 |nds to a| Y value|
|00001530| 20 28 74 79 70 69 63 61 | 6c 6c 79 20 32 5e 36 20 | (typica|lly 2^6 |
|00001540| 3d 20 36 34 20 70 6f 69 | 6e 74 65 72 73 29 20 61 |= 64 poi|nters) a|
|00001550| 6e 64 0a 58 20 2a 20 65 | 61 63 68 20 32 2d 44 20 |nd.X * e|ach 2-D |
|00001560| 61 72 72 61 79 20 68 61 | 73 20 32 5e 35 5e 32 20 |array ha|s 2^5^2 |
|00001570| 3d 20 31 30 32 34 20 6f | 72 20 32 5e 36 5e 32 20 |= 1024 o|r 2^6^2 |
|00001580| 3d 20 34 30 39 36 20 65 | 6e 74 72 69 65 73 2e 20 |= 4096 e|ntries. |
|00001590| 20 4e 6f 74 65 20 74 68 | 61 74 0a 58 20 2a 20 6f | Note th|at.X * o|
|000015a0| 6e 20 38 30 78 38 36 20 | 6d 61 63 68 69 6e 65 73 |n 80x86 |machines|
|000015b0| 2c 20 74 68 65 20 70 6f | 69 6e 74 65 72 20 72 6f |, the po|inter ro|
|000015c0| 77 20 69 73 20 69 6e 20 | 6e 65 61 72 20 6d 65 6d |w is in |near mem|
|000015d0| 6f 72 79 20 62 75 74 20 | 74 68 65 20 61 63 74 75 |ory but |the actu|
|000015e0| 61 6c 0a 58 20 2a 20 61 | 72 72 61 79 73 20 61 72 |al.X * a|rrays ar|
|000015f0| 65 20 69 6e 20 66 61 72 | 20 6d 65 6d 6f 72 79 20 |e in far| memory |
|00001600| 28 73 61 6d 65 20 61 72 | 72 61 6e 67 65 6d 65 6e |(same ar|rangemen|
|00001610| 74 20 61 73 20 77 65 20 | 75 73 65 20 66 6f 72 20 |t as we |use for |
|00001620| 69 6d 61 67 65 20 61 72 | 72 61 79 73 29 2e 0a 58 |image ar|rays)..X|
|00001630| 20 2a 2f 0a 58 0a 58 23 | 69 66 6e 64 65 66 20 48 | */.X.X#|ifndef H|
|00001640| 49 53 54 5f 59 5f 42 49 | 54 53 09 09 2f 2a 20 73 |IST_Y_BI|TS../* s|
|00001650| 6f 20 79 6f 75 20 63 61 | 6e 20 6f 76 65 72 72 69 |o you ca|n overri|
|00001660| 64 65 20 66 72 6f 6d 20 | 4d 61 6b 65 66 69 6c 65 |de from |Makefile|
|00001670| 20 2a 2f 0a 58 23 64 65 | 66 69 6e 65 20 48 49 53 | */.X#de|fine HIS|
|00001680| 54 5f 59 5f 42 49 54 53 | 20 20 36 09 09 2f 2a 20 |T_Y_BITS| 6../* |
|00001690| 62 69 74 73 20 6f 66 20 | 70 72 65 63 69 73 69 6f |bits of |precisio|
|000016a0| 6e 20 69 6e 20 59 20 68 | 69 73 74 6f 67 72 61 6d |n in Y h|istogram|
|000016b0| 20 2a 2f 0a 58 23 65 6e | 64 69 66 0a 58 23 69 66 | */.X#en|dif.X#if|
|000016c0| 6e 64 65 66 20 48 49 53 | 54 5f 43 5f 42 49 54 53 |ndef HIS|T_C_BITS|
|000016d0| 09 09 2f 2a 20 73 6f 20 | 79 6f 75 20 63 61 6e 20 |../* so |you can |
|000016e0| 6f 76 65 72 72 69 64 65 | 20 66 72 6f 6d 20 4d 61 |override| from Ma|
|000016f0| 6b 65 66 69 6c 65 20 2a | 2f 0a 58 23 64 65 66 69 |kefile *|/.X#defi|
|00001700| 6e 65 20 48 49 53 54 5f | 43 5f 42 49 54 53 20 20 |ne HIST_|C_BITS |
|00001710| 35 09 09 2f 2a 20 62 69 | 74 73 20 6f 66 20 70 72 |5../* bi|ts of pr|
|00001720| 65 63 69 73 69 6f 6e 20 | 69 6e 20 43 62 2f 43 72 |ecision |in Cb/Cr|
|00001730| 20 68 69 73 74 6f 67 72 | 61 6d 20 2a 2f 0a 58 23 | histogr|am */.X#|
|00001740| 65 6e 64 69 66 0a 58 0a | 58 23 64 65 66 69 6e 65 |endif.X.|X#define|
|00001750| 20 48 49 53 54 5f 59 5f | 45 4c 45 4d 53 20 20 28 | HIST_Y_|ELEMS (|
|00001760| 31 3c 3c 48 49 53 54 5f | 59 5f 42 49 54 53 29 20 |1<<HIST_|Y_BITS) |
|00001770| 2f 2a 20 23 20 6f 66 20 | 65 6c 65 6d 65 6e 74 73 |/* # of |elements|
|00001780| 20 61 6c 6f 6e 67 20 68 | 69 73 74 6f 67 72 61 6d | along h|istogram|
|00001790| 20 61 78 65 73 20 2a 2f | 0a 58 23 64 65 66 69 6e | axes */|.X#defin|
|000017a0| 65 20 48 49 53 54 5f 43 | 5f 45 4c 45 4d 53 20 20 |e HIST_C|_ELEMS |
|000017b0| 28 31 3c 3c 48 49 53 54 | 5f 43 5f 42 49 54 53 29 |(1<<HIST|_C_BITS)|
|000017c0| 0a 58 0a 58 2f 2a 20 54 | 68 65 73 65 20 61 72 65 |.X.X/* T|hese are|
|000017d0| 20 74 68 65 20 61 6d 6f | 75 6e 74 73 20 74 6f 20 | the amo|unts to |
|000017e0| 73 68 69 66 74 20 61 6e | 20 69 6e 70 75 74 20 76 |shift an| input v|
|000017f0| 61 6c 75 65 20 74 6f 20 | 67 65 74 20 61 20 68 69 |alue to |get a hi|
|00001800| 73 74 6f 67 72 61 6d 20 | 69 6e 64 65 78 2e 0a 58 |stogram |index..X|
|00001810| 20 2a 20 46 6f 72 20 61 | 20 63 6f 6d 62 69 6e 61 | * For a| combina|
|00001820| 74 69 6f 6e 20 38 2f 31 | 32 20 62 69 74 20 69 6d |tion 8/1|2 bit im|
|00001830| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 2c 20 77 6f |plementa|tion, wo|
|00001840| 75 6c 64 20 6e 65 65 64 | 20 76 61 72 69 61 62 6c |uld need| variabl|
|00001850| 65 73 20 68 65 72 65 2e | 2e 2e 0a 58 20 2a 2f 0a |es here.|...X */.|
|00001860| 58 0a 58 23 64 65 66 69 | 6e 65 20 59 5f 53 48 49 |X.X#defi|ne Y_SHI|
|00001870| 46 54 20 20 28 42 49 54 | 53 5f 49 4e 5f 4a 53 41 |FT (BIT|S_IN_JSA|
|00001880| 4d 50 4c 45 2d 48 49 53 | 54 5f 59 5f 42 49 54 53 |MPLE-HIS|T_Y_BITS|
|00001890| 29 0a 58 23 64 65 66 69 | 6e 65 20 43 5f 53 48 49 |).X#defi|ne C_SHI|
|000018a0| 46 54 20 20 28 42 49 54 | 53 5f 49 4e 5f 4a 53 41 |FT (BIT|S_IN_JSA|
|000018b0| 4d 50 4c 45 2d 48 49 53 | 54 5f 43 5f 42 49 54 53 |MPLE-HIS|T_C_BITS|
|000018c0| 29 0a 58 0a 58 0a 58 74 | 79 70 65 64 65 66 20 55 |).X.X.Xt|ypedef U|
|000018d0| 49 4e 54 31 36 20 68 69 | 73 74 63 65 6c 6c 3b 09 |INT16 hi|stcell;.|
|000018e0| 2f 2a 20 68 69 73 74 6f | 67 72 61 6d 20 63 65 6c |/* histo|gram cel|
|000018f0| 6c 3b 20 4d 55 53 54 20 | 62 65 20 61 6e 20 75 6e |l; MUST |be an un|
|00001900| 73 69 67 6e 65 64 20 74 | 79 70 65 20 2a 2f 0a 58 |signed t|ype */.X|
|00001910| 0a 58 74 79 70 65 64 65 | 66 20 68 69 73 74 63 65 |.Xtypede|f histce|
|00001920| 6c 6c 20 46 41 52 20 2a | 20 68 69 73 74 70 74 72 |ll FAR *| histptr|
|00001930| 3b 09 2f 2a 20 66 6f 72 | 20 70 6f 69 6e 74 65 72 |;./* for| pointer|
|00001940| 73 20 74 6f 20 68 69 73 | 74 6f 67 72 61 6d 20 63 |s to his|togram c|
|00001950| 65 6c 6c 73 20 2a 2f 0a | 58 0a 58 74 79 70 65 64 |ells */.|X.Xtyped|
|00001960| 65 66 20 68 69 73 74 63 | 65 6c 6c 20 68 69 73 74 |ef histc|ell hist|
|00001970| 31 64 5b 48 49 53 54 5f | 43 5f 45 4c 45 4d 53 5d |1d[HIST_|C_ELEMS]|
|00001980| 3b 20 2f 2a 20 74 79 70 | 65 64 65 66 73 20 66 6f |; /* typ|edefs fo|
|00001990| 72 20 74 68 65 20 61 72 | 72 61 79 20 2a 2f 0a 58 |r the ar|ray */.X|
|000019a0| 74 79 70 65 64 65 66 20 | 68 69 73 74 31 64 20 46 |typedef |hist1d F|
|000019b0| 41 52 20 2a 20 68 69 73 | 74 32 64 3b 09 2f 2a 20 |AR * his|t2d;./* |
|000019c0| 74 79 70 65 20 66 6f 72 | 20 74 68 65 20 59 2d 6c |type for| the Y-l|
|000019d0| 65 76 65 6c 20 70 6f 69 | 6e 74 65 72 73 20 2a 2f |evel poi|nters */|
|000019e0| 0a 58 74 79 70 65 64 65 | 66 20 68 69 73 74 32 64 |.Xtypede|f hist2d|
|000019f0| 20 2a 20 68 69 73 74 33 | 64 3b 09 2f 2a 20 74 79 | * hist3|d;./* ty|
|00001a00| 70 65 20 66 6f 72 20 74 | 6f 70 2d 6c 65 76 65 6c |pe for t|op-level|
|00001a10| 20 70 6f 69 6e 74 65 72 | 20 2a 2f 0a 58 0a 58 73 | pointer| */.X.Xs|
|00001a20| 74 61 74 69 63 20 68 69 | 73 74 33 64 20 68 69 73 |tatic hi|st3d his|
|00001a30| 74 6f 67 72 61 6d 3b 09 | 2f 2a 20 70 6f 69 6e 74 |togram;.|/* point|
|00001a40| 65 72 20 74 6f 20 74 68 | 65 20 68 69 73 74 6f 67 |er to th|e histog|
|00001a50| 72 61 6d 20 2a 2f 0a 58 | 0a 58 0a 58 2f 2a 0a 58 |ram */.X|.X.X/*.X|
|00001a60| 20 2a 20 50 72 65 73 63 | 61 6e 20 73 6f 6d 65 20 | * Presc|an some |
|00001a70| 72 6f 77 73 20 6f 66 20 | 70 69 78 65 6c 73 2e 0a |rows of |pixels..|
|00001a80| 58 20 2a 20 49 6e 20 74 | 68 69 73 20 6d 6f 64 75 |X * In t|his modu|
|00001a90| 6c 65 20 74 68 65 20 70 | 72 65 73 63 61 6e 20 73 |le the p|rescan s|
|00001aa0| 69 6d 70 6c 79 20 75 70 | 64 61 74 65 73 20 74 68 |imply up|dates th|
|00001ab0| 65 20 68 69 73 74 6f 67 | 72 61 6d 2c 20 77 68 69 |e histog|ram, whi|
|00001ac0| 63 68 20 68 61 73 20 62 | 65 65 6e 0a 58 20 2a 20 |ch has b|een.X * |
|00001ad0| 69 6e 69 74 69 61 6c 69 | 7a 65 64 20 74 6f 20 7a |initiali|zed to z|
|00001ae0| 65 72 6f 65 73 20 62 79 | 20 63 6f 6c 6f 72 5f 71 |eroes by| color_q|
|00001af0| 75 61 6e 74 5f 69 6e 69 | 74 2e 0a 58 20 2a 20 4e |uant_ini|t..X * N|
|00001b00| 6f 74 65 3a 20 77 6f 72 | 6b 73 70 61 63 65 20 69 |ote: wor|kspace i|
|00001b10| 73 20 70 72 6f 62 61 62 | 6c 79 20 6e 6f 74 20 75 |s probab|ly not u|
|00001b20| 73 65 66 75 6c 20 66 6f | 72 20 74 68 69 73 20 72 |seful fo|r this r|
|00001b30| 6f 75 74 69 6e 65 2c 20 | 62 75 74 20 69 74 20 69 |outine, |but it i|
|00001b40| 73 20 70 61 73 73 65 64 | 0a 58 20 2a 20 61 6e 79 |s passed|.X * any|
|00001b50| 77 61 79 20 74 6f 20 61 | 6c 6c 6f 77 20 73 6f 6d |way to a|llow som|
|00001b60| 65 20 63 6f 64 65 20 73 | 68 61 72 69 6e 67 20 77 |e code s|haring w|
|00001b70| 69 74 68 69 6e 20 74 68 | 65 20 70 69 70 65 6c 69 |ithin th|e pipeli|
|00001b80| 6e 65 20 63 6f 6e 74 72 | 6f 6c 6c 65 72 2e 0a 58 |ne contr|oller..X|
|00001b90| 20 2a 2f 0a 58 0a 58 4d | 45 54 48 4f 44 44 45 46 | */.X.XM|ETHODDEF|
|00001ba0| 20 76 6f 69 64 0a 58 63 | 6f 6c 6f 72 5f 71 75 61 | void.Xc|olor_qua|
|00001bb0| 6e 74 5f 70 72 65 73 63 | 61 6e 20 28 64 65 63 6f |nt_presc|an (deco|
|00001bc0| 6d 70 72 65 73 73 5f 69 | 6e 66 6f 5f 70 74 72 20 |mpress_i|nfo_ptr |
|00001bd0| 63 69 6e 66 6f 2c 20 69 | 6e 74 20 6e 75 6d 5f 72 |cinfo, i|nt num_r|
|00001be0| 6f 77 73 2c 0a 58 09 09 | 20 20 20 20 20 4a 53 41 |ows,.X..| JSA|
|00001bf0| 4d 50 49 4d 41 47 45 20 | 69 6d 61 67 65 5f 64 61 |MPIMAGE |image_da|
|00001c00| 74 61 2c 20 4a 53 41 4d | 50 41 52 52 41 59 20 77 |ta, JSAM|PARRAY w|
|00001c10| 6f 72 6b 73 70 61 63 65 | 29 0a 58 7b 0a 58 20 20 |orkspace|).X{.X |
|00001c20| 72 65 67 69 73 74 65 72 | 20 4a 53 41 4d 50 52 4f |register| JSAMPRO|
|00001c30| 57 20 70 74 72 30 2c 20 | 70 74 72 31 2c 20 70 74 |W ptr0, |ptr1, pt|
|00001c40| 72 32 3b 0a 58 20 20 72 | 65 67 69 73 74 65 72 20 |r2;.X r|egister |
|00001c50| 68 69 73 74 70 74 72 20 | 68 69 73 74 70 3b 0a 58 |histptr |histp;.X|
|00001c60| 20 20 72 65 67 69 73 74 | 65 72 20 69 6e 74 20 63 | regist|er int c|
|00001c70| 30 2c 20 63 31 2c 20 63 | 32 3b 0a 58 20 20 69 6e |0, c1, c|2;.X in|
|00001c80| 74 20 72 6f 77 3b 0a 58 | 20 20 6c 6f 6e 67 20 63 |t row;.X| long c|
|00001c90| 6f 6c 3b 0a 58 20 20 6c | 6f 6e 67 20 77 69 64 74 |ol;.X l|ong widt|
|00001ca0| 68 20 3d 20 63 69 6e 66 | 6f 2d 3e 69 6d 61 67 65 |h = cinf|o->image|
|00001cb0| 5f 77 69 64 74 68 3b 0a | 58 0a 58 20 20 66 6f 72 |_width;.|X.X for|
|00001cc0| 20 28 72 6f 77 20 3d 20 | 30 3b 20 72 6f 77 20 3c | (row = |0; row <|
|00001cd0| 20 6e 75 6d 5f 72 6f 77 | 73 3b 20 72 6f 77 2b 2b | num_row|s; row++|
|00001ce0| 29 20 7b 0a 58 20 20 20 | 20 70 74 72 30 20 3d 20 |) {.X | ptr0 = |
|00001cf0| 69 6d 61 67 65 5f 64 61 | 74 61 5b 30 5d 5b 72 6f |image_da|ta[0][ro|
|00001d00| 77 5d 3b 0a 58 20 20 20 | 20 70 74 72 31 20 3d 20 |w];.X | ptr1 = |
|00001d10| 69 6d 61 67 65 5f 64 61 | 74 61 5b 31 5d 5b 72 6f |image_da|ta[1][ro|
|00001d20| 77 5d 3b 0a 58 20 20 20 | 20 70 74 72 32 20 3d 20 |w];.X | ptr2 = |
|00001d30| 69 6d 61 67 65 5f 64 61 | 74 61 5b 32 5d 5b 72 6f |image_da|ta[2][ro|
|00001d40| 77 5d 3b 0a 58 20 20 20 | 20 66 6f 72 20 28 63 6f |w];.X | for (co|
|00001d50| 6c 20 3d 20 77 69 64 74 | 68 3b 20 63 6f 6c 20 3e |l = widt|h; col >|
|00001d60| 20 30 3b 20 63 6f 6c 2d | 2d 29 20 7b 0a 58 20 20 | 0; col-|-) {.X |
|00001d70| 20 20 20 20 2f 2a 20 67 | 65 74 20 70 69 78 65 6c | /* g|et pixel|
|00001d80| 20 76 61 6c 75 65 20 61 | 6e 64 20 69 6e 64 65 78 | value a|nd index|
|00001d90| 20 69 6e 74 6f 20 74 68 | 65 20 68 69 73 74 6f 67 | into th|e histog|
|00001da0| 72 61 6d 20 2a 2f 0a 58 | 20 20 20 20 20 20 63 30 |ram */.X| c0|
|00001db0| 20 3d 20 47 45 54 4a 53 | 41 4d 50 4c 45 28 2a 70 | = GETJS|AMPLE(*p|
|00001dc0| 74 72 30 2b 2b 29 20 3e | 3e 20 59 5f 53 48 49 46 |tr0++) >|> Y_SHIF|
|00001dd0| 54 3b 0a 58 20 20 20 20 | 20 20 63 31 20 3d 20 47 |T;.X | c1 = G|
|00001de0| 45 54 4a 53 41 4d 50 4c | 45 28 2a 70 74 72 31 2b |ETJSAMPL|E(*ptr1+|
|00001df0| 2b 29 20 3e 3e 20 43 5f | 53 48 49 46 54 3b 0a 58 |+) >> C_|SHIFT;.X|
|00001e00| 20 20 20 20 20 20 63 32 | 20 3d 20 47 45 54 4a 53 | c2| = GETJS|
|00001e10| 41 4d 50 4c 45 28 2a 70 | 74 72 32 2b 2b 29 20 3e |AMPLE(*p|tr2++) >|
|00001e20| 3e 20 43 5f 53 48 49 46 | 54 3b 0a 58 20 20 20 20 |> C_SHIF|T;.X |
|00001e30| 20 20 68 69 73 74 70 20 | 3d 20 26 20 68 69 73 74 | histp |= & hist|
|00001e40| 6f 67 72 61 6d 5b 63 30 | 5d 5b 63 31 5d 5b 63 32 |ogram[c0|][c1][c2|
|00001e50| 5d 3b 0a 58 20 20 20 20 | 20 20 2f 2a 20 69 6e 63 |];.X | /* inc|
|00001e60| 72 65 6d 65 6e 74 2c 20 | 63 68 65 63 6b 20 66 6f |rement, |check fo|
|00001e70| 72 20 6f 76 65 72 66 6c | 6f 77 20 61 6e 64 20 75 |r overfl|ow and u|
|00001e80| 6e 64 6f 20 69 6e 63 72 | 65 6d 65 6e 74 20 69 66 |ndo incr|ement if|
|00001e90| 20 73 6f 2e 20 2a 2f 0a | 58 20 20 20 20 20 20 2f | so. */.|X /|
|00001ea0| 2a 20 57 65 20 61 73 73 | 75 6d 65 20 75 6e 73 69 |* We ass|ume unsi|
|00001eb0| 67 6e 65 64 20 72 65 70 | 72 65 73 65 6e 74 61 74 |gned rep|resentat|
|00001ec0| 69 6f 6e 20 68 65 72 65 | 21 20 2a 2f 0a 58 20 20 |ion here|! */.X |
|00001ed0| 20 20 20 20 69 66 20 28 | 2b 2b 28 2a 68 69 73 74 | if (|++(*hist|
|00001ee0| 70 29 20 3d 3d 20 30 29 | 0a 58 09 28 2a 68 69 73 |p) == 0)|.X.(*his|
|00001ef0| 74 70 29 2d 2d 3b 0a 58 | 20 20 20 20 7d 0a 58 20 |tp)--;.X| }.X |
|00001f00| 20 7d 0a 58 7d 0a 58 0a | 58 0a 58 2f 2a 0a 58 20 | }.X}.X.|X.X/*.X |
|00001f10| 2a 20 4e 6f 77 20 77 65 | 20 68 61 76 65 20 74 68 |* Now we| have th|
|00001f20| 65 20 72 65 61 6c 6c 79 | 20 69 6e 74 65 72 65 73 |e really| interes|
|00001f30| 74 69 6e 67 20 72 6f 75 | 74 69 6e 65 73 3a 20 73 |ting rou|tines: s|
|00001f40| 65 6c 65 63 74 69 6f 6e | 20 6f 66 20 61 20 63 6f |election| of a co|
|00001f50| 6c 6f 72 6d 61 70 0a 58 | 20 2a 20 67 69 76 65 6e |lormap.X| * given|
|00001f60| 20 74 68 65 20 63 6f 6d | 70 6c 65 74 65 64 20 68 | the com|pleted h|
|00001f70| 69 73 74 6f 67 72 61 6d | 2e 0a 58 20 2a 20 54 68 |istogram|..X * Th|
|00001f80| 65 73 65 20 72 6f 75 74 | 69 6e 65 73 20 77 6f 72 |ese rout|ines wor|
|00001f90| 6b 20 77 69 74 68 20 61 | 20 6c 69 73 74 20 6f 66 |k with a| list of|
|00001fa0| 20 22 62 6f 78 65 73 22 | 2c 20 65 61 63 68 20 72 | "boxes"|, each r|
|00001fb0| 65 70 72 65 73 65 6e 74 | 69 6e 67 20 61 20 72 65 |epresent|ing a re|
|00001fc0| 63 74 61 6e 67 75 6c 61 | 72 0a 58 20 2a 20 73 75 |ctangula|r.X * su|
|00001fd0| 62 73 65 74 20 6f 66 20 | 74 68 65 20 69 6e 70 75 |bset of |the inpu|
|00001fe0| 74 20 63 6f 6c 6f 72 20 | 73 70 61 63 65 20 28 74 |t color |space (t|
|00001ff0| 6f 20 68 69 73 74 6f 67 | 72 61 6d 20 70 72 65 63 |o histog|ram prec|
|00002000| 69 73 69 6f 6e 29 2e 0a | 58 20 2a 2f 0a 58 0a 58 |ision)..|X */.X.X|
|00002010| 74 79 70 65 64 65 66 20 | 73 74 72 75 63 74 20 7b |typedef |struct {|
|00002020| 0a 58 09 2f 2a 20 54 68 | 65 20 62 6f 75 6e 64 73 |.X./* Th|e bounds|
|00002030| 20 6f 66 20 74 68 65 20 | 62 6f 78 20 28 69 6e 63 | of the |box (inc|
|00002040| 6c 75 73 69 76 65 29 3b | 20 65 78 70 72 65 73 73 |lusive);| express|
|00002050| 65 64 20 61 73 20 68 69 | 73 74 6f 67 72 61 6d 20 |ed as hi|stogram |
|00002060| 69 6e 64 65 78 65 73 20 | 2a 2f 0a 58 09 69 6e 74 |indexes |*/.X.int|
|00002070| 20 63 30 6d 69 6e 2c 20 | 63 30 6d 61 78 3b 0a 58 | c0min, |c0max;.X|
|00002080| 09 69 6e 74 20 63 31 6d | 69 6e 2c 20 63 31 6d 61 |.int c1m|in, c1ma|
|00002090| 78 3b 0a 58 09 69 6e 74 | 20 63 32 6d 69 6e 2c 20 |x;.X.int| c2min, |
|000020a0| 63 32 6d 61 78 3b 0a 58 | 09 2f 2a 20 54 68 65 20 |c2max;.X|./* The |
|000020b0| 6e 75 6d 62 65 72 20 6f | 66 20 6e 6f 6e 7a 65 72 |number o|f nonzer|
|000020c0| 6f 20 68 69 73 74 6f 67 | 72 61 6d 20 63 65 6c 6c |o histog|ram cell|
|000020d0| 73 20 77 69 74 68 69 6e | 20 74 68 69 73 20 62 6f |s within| this bo|
|000020e0| 78 20 2a 2f 0a 58 09 6c | 6f 6e 67 20 63 6f 6c 6f |x */.X.l|ong colo|
|000020f0| 72 63 6f 75 6e 74 3b 0a | 58 20 20 20 20 20 20 7d |rcount;.|X }|
|00002100| 20 62 6f 78 3b 0a 58 74 | 79 70 65 64 65 66 20 62 | box;.Xt|ypedef b|
|00002110| 6f 78 20 2a 20 62 6f 78 | 70 74 72 3b 0a 58 0a 58 |ox * box|ptr;.X.X|
|00002120| 73 74 61 74 69 63 20 62 | 6f 78 70 74 72 20 62 6f |static b|oxptr bo|
|00002130| 78 6c 69 73 74 3b 09 09 | 2f 2a 20 61 72 72 61 79 |xlist;..|/* array|
|00002140| 20 77 69 74 68 20 72 6f | 6f 6d 20 66 6f 72 20 64 | with ro|om for d|
|00002150| 65 73 69 72 65 64 20 23 | 20 6f 66 20 62 6f 78 65 |esired #| of boxe|
|00002160| 73 20 2a 2f 0a 58 73 74 | 61 74 69 63 20 69 6e 74 |s */.Xst|atic int|
|00002170| 20 6e 75 6d 62 6f 78 65 | 73 3b 09 09 2f 2a 20 6e | numboxe|s;../* n|
|00002180| 75 6d 62 65 72 20 6f 66 | 20 62 6f 78 65 73 20 63 |umber of| boxes c|
|00002190| 75 72 72 65 6e 74 6c 79 | 20 69 6e 20 62 6f 78 6c |urrently| in boxl|
|000021a0| 69 73 74 20 2a 2f 0a 58 | 0a 58 73 74 61 74 69 63 |ist */.X|.Xstatic|
|000021b0| 20 4a 53 41 4d 50 41 52 | 52 41 59 20 6d 79 5f 63 | JSAMPAR|RAY my_c|
|000021c0| 6f 6c 6f 72 6d 61 70 3b | 09 2f 2a 20 74 68 65 20 |olormap;|./* the |
|000021d0| 66 69 6e 69 73 68 65 64 | 20 63 6f 6c 6f 72 6d 61 |finished| colorma|
|000021e0| 70 20 28 69 6e 20 59 43 | 62 43 72 20 73 70 61 63 |p (in YC|bCr spac|
|000021f0| 65 29 20 2a 2f 0a 58 0a | 58 0a 58 4c 4f 43 41 4c |e) */.X.|X.XLOCAL|
|00002200| 20 62 6f 78 70 74 72 0a | 58 66 69 6e 64 5f 62 69 | boxptr.|Xfind_bi|
|00002210| 67 67 65 73 74 5f 63 6f | 6c 6f 72 5f 70 6f 70 20 |ggest_co|lor_pop |
|00002220| 28 76 6f 69 64 29 0a 58 | 2f 2a 20 46 69 6e 64 20 |(void).X|/* Find |
|00002230| 74 68 65 20 73 70 6c 69 | 74 74 61 62 6c 65 20 62 |the spli|ttable b|
|00002240| 6f 78 20 77 69 74 68 20 | 74 68 65 20 6c 61 72 67 |ox with |the larg|
|00002250| 65 73 74 20 63 6f 6c 6f | 72 20 70 6f 70 75 6c 61 |est colo|r popula|
|00002260| 74 69 6f 6e 20 2a 2f 0a | 58 2f 2a 20 52 65 74 75 |tion */.|X/* Retu|
|00002270| 72 6e 73 20 4e 55 4c 4c | 20 69 66 20 6e 6f 20 73 |rns NULL| if no s|
|00002280| 70 6c 69 74 74 61 62 6c | 65 20 62 6f 78 65 73 20 |plittabl|e boxes |
|00002290| 72 65 6d 61 69 6e 20 2a | 2f 0a 58 7b 0a 58 20 20 |remain *|/.X{.X |
|000022a0| 72 65 67 69 73 74 65 72 | 20 62 6f 78 70 74 72 20 |register| boxptr |
|000022b0| 62 6f 78 70 3b 0a 58 20 | 20 72 65 67 69 73 74 65 |boxp;.X | registe|
|000022c0| 72 20 69 6e 74 20 69 3b | 0a 58 20 20 72 65 67 69 |r int i;|.X regi|
|000022d0| 73 74 65 72 20 6c 6f 6e | 67 20 6d 61 78 20 3d 20 |ster lon|g max = |
|000022e0| 30 3b 0a 58 20 20 62 6f | 78 70 74 72 20 77 68 69 |0;.X bo|xptr whi|
|000022f0| 63 68 20 3d 20 4e 55 4c | 4c 3b 0a 58 20 20 0a 58 |ch = NUL|L;.X .X|
|00002300| 20 20 66 6f 72 20 28 69 | 20 3d 20 30 2c 20 62 6f | for (i| = 0, bo|
|00002310| 78 70 20 3d 20 62 6f 78 | 6c 69 73 74 3b 20 69 20 |xp = box|list; i |
|00002320| 3c 20 6e 75 6d 62 6f 78 | 65 73 3b 20 69 2b 2b 2c |< numbox|es; i++,|
|00002330| 20 62 6f 78 70 2b 2b 29 | 20 7b 0a 58 20 20 20 20 | boxp++)| {.X |
|00002340| 69 66 20 28 62 6f 78 70 | 2d 3e 63 6f 6c 6f 72 63 |if (boxp|->colorc|
|00002350| 6f 75 6e 74 20 3e 20 6d | 61 78 29 20 7b 0a 58 20 |ount > m|ax) {.X |
|00002360| 20 20 20 20 20 69 66 20 | 28 62 6f 78 70 2d 3e 63 | if |(boxp->c|
|00002370| 30 6d 61 78 20 3e 20 62 | 6f 78 70 2d 3e 63 30 6d |0max > b|oxp->c0m|
|00002380| 69 6e 20 7c 7c 20 62 6f | 78 70 2d 3e 63 31 6d 61 |in || bo|xp->c1ma|
|00002390| 78 20 3e 20 62 6f 78 70 | 2d 3e 63 31 6d 69 6e 20 |x > boxp|->c1min |
|000023a0| 7c 7c 0a 58 09 20 20 62 | 6f 78 70 2d 3e 63 32 6d |||.X. b|oxp->c2m|
|000023b0| 61 78 20 3e 20 62 6f 78 | 70 2d 3e 63 32 6d 69 6e |ax > box|p->c2min|
|000023c0| 29 20 7b 0a 58 09 77 68 | 69 63 68 20 3d 20 62 6f |) {.X.wh|ich = bo|
|000023d0| 78 70 3b 0a 58 09 6d 61 | 78 20 3d 20 62 6f 78 70 |xp;.X.ma|x = boxp|
|000023e0| 2d 3e 63 6f 6c 6f 72 63 | 6f 75 6e 74 3b 0a 58 20 |->colorc|ount;.X |
|000023f0| 20 20 20 20 20 7d 0a 58 | 20 20 20 20 7d 0a 58 20 | }.X| }.X |
|00002400| 20 7d 0a 58 20 20 72 65 | 74 75 72 6e 20 77 68 69 | }.X re|turn whi|
|00002410| 63 68 3b 0a 58 7d 0a 58 | 0a 58 0a 58 4c 4f 43 41 |ch;.X}.X|.X.XLOCA|
|00002420| 4c 20 62 6f 78 70 74 72 | 0a 58 66 69 6e 64 5f 62 |L boxptr|.Xfind_b|
|00002430| 69 67 67 65 73 74 5f 76 | 6f 6c 75 6d 65 20 28 76 |iggest_v|olume (v|
|00002440| 6f 69 64 29 0a 58 2f 2a | 20 46 69 6e 64 20 74 68 |oid).X/*| Find th|
|00002450| 65 20 73 70 6c 69 74 74 | 61 62 6c 65 20 62 6f 78 |e splitt|able box|
|00002460| 20 77 69 74 68 20 74 68 | 65 20 6c 61 72 67 65 73 | with th|e larges|
|00002470| 74 20 28 73 63 61 6c 65 | 64 29 20 76 6f 6c 75 6d |t (scale|d) volum|
|00002480| 65 20 2a 2f 0a 58 2f 2a | 20 52 65 74 75 72 6e 73 |e */.X/*| Returns|
|00002490| 20 4e 55 4c 4c 20 69 66 | 20 6e 6f 20 73 70 6c 69 | NULL if| no spli|
|000024a0| 74 74 61 62 6c 65 20 62 | 6f 78 65 73 20 72 65 6d |ttable b|oxes rem|
|000024b0| 61 69 6e 20 2a 2f 0a 58 | 7b 0a 58 20 20 72 65 67 |ain */.X|{.X reg|
|000024c0| 69 73 74 65 72 20 62 6f | 78 70 74 72 20 62 6f 78 |ister bo|xptr box|
|000024d0| 70 3b 0a 58 20 20 72 65 | 67 69 73 74 65 72 20 69 |p;.X re|gister i|
|000024e0| 6e 74 20 69 3b 0a 58 20 | 20 72 65 67 69 73 74 65 |nt i;.X | registe|
|000024f0| 72 20 49 4e 54 33 32 20 | 6d 61 78 20 3d 20 30 3b |r INT32 |max = 0;|
|00002500| 0a 58 20 20 72 65 67 69 | 73 74 65 72 20 49 4e 54 |.X regi|ster INT|
|00002510| 33 32 20 6e 6f 72 6d 2c | 20 63 30 2c 63 31 2c 63 |32 norm,| c0,c1,c|
|00002520| 32 3b 0a 58 20 20 62 6f | 78 70 74 72 20 77 68 69 |2;.X bo|xptr whi|
|00002530| 63 68 20 3d 20 4e 55 4c | 4c 3b 0a 58 20 20 0a 58 |ch = NUL|L;.X .X|
|00002540| 20 20 2f 2a 20 57 65 20 | 75 73 65 20 32 2d 6e 6f | /* We |use 2-no|
|00002550| 72 6d 20 72 61 74 68 65 | 72 20 74 68 61 6e 20 72 |rm rathe|r than r|
|00002560| 65 61 6c 20 76 6f 6c 75 | 6d 65 20 68 65 72 65 2e |eal volu|me here.|
|00002570| 0a 58 20 20 20 2a 20 53 | 6f 6d 65 20 63 61 72 65 |.X * S|ome care|
|00002580| 20 69 73 20 6e 65 65 64 | 65 64 20 73 69 6e 63 65 | is need|ed since|
|00002590| 20 74 68 65 20 64 69 66 | 66 65 72 65 6e 63 65 73 | the dif|ferences|
|000025a0| 20 61 72 65 20 65 78 70 | 72 65 73 73 65 64 20 69 | are exp|ressed i|
|000025b0| 6e 0a 58 20 20 20 2a 20 | 68 69 73 74 6f 67 72 61 |n.X * |histogra|
|000025c0| 6d 2d 63 65 6c 6c 20 75 | 6e 69 74 73 3b 20 69 66 |m-cell u|nits; if|
|000025d0| 20 48 49 53 54 5f 59 5f | 42 49 54 53 20 21 3d 20 | HIST_Y_|BITS != |
|000025e0| 48 49 53 54 5f 43 5f 42 | 49 54 53 2c 20 77 65 20 |HIST_C_B|ITS, we |
|000025f0| 68 61 76 65 20 74 6f 0a | 58 20 20 20 2a 20 61 64 |have to.|X * ad|
|00002600| 6a 75 73 74 20 74 68 65 | 20 73 63 61 6c 69 6e 67 |just the| scaling|
|00002610| 20 74 6f 20 67 65 74 20 | 74 68 65 20 70 72 6f 70 | to get |the prop|
|00002620| 65 72 20 73 63 61 6c 65 | 64 2d 59 43 62 43 72 2d |er scale|d-YCbCr-|
|00002630| 73 70 61 63 65 20 64 69 | 73 74 61 6e 63 65 2e 0a |space di|stance..|
|00002640| 58 20 20 20 2a 20 54 68 | 69 73 20 63 6f 64 65 20 |X * Th|is code |
|00002650| 77 6f 6e 27 74 20 77 6f | 72 6b 20 72 69 67 68 74 |won't wo|rk right|
|00002660| 20 69 66 20 48 49 53 54 | 5f 59 5f 42 49 54 53 20 | if HIST|_Y_BITS |
|00002670| 3c 20 48 49 53 54 5f 43 | 5f 42 49 54 53 2c 0a 58 |< HIST_C|_BITS,.X|
|00002680| 20 20 20 2a 20 62 75 74 | 20 74 68 61 74 20 73 68 | * but| that sh|
|00002690| 6f 75 6c 64 6e 27 74 20 | 65 76 65 72 20 62 65 20 |ouldn't |ever be |
|000026a0| 74 72 75 65 2e 0a 58 20 | 20 20 2a 20 4e 6f 74 65 |true..X | * Note|
|000026b0| 20 6e 6f 72 6d 20 3e 20 | 30 20 69 66 66 20 62 6f | norm > |0 iff bo|
|000026c0| 78 20 69 73 20 73 70 6c | 69 74 74 61 62 6c 65 2c |x is spl|ittable,|
|000026d0| 20 73 6f 20 6e 65 65 64 | 20 6e 6f 74 20 63 68 65 | so need| not che|
|000026e0| 63 6b 20 73 65 70 61 72 | 61 74 65 6c 79 2e 0a 58 |ck separ|ately..X|
|000026f0| 20 20 20 2a 2f 0a 58 20 | 20 0a 58 20 20 66 6f 72 | */.X | .X for|
|00002700| 20 28 69 20 3d 20 30 2c | 20 62 6f 78 70 20 3d 20 | (i = 0,| boxp = |
|00002710| 62 6f 78 6c 69 73 74 3b | 20 69 20 3c 20 6e 75 6d |boxlist;| i < num|
|00002720| 62 6f 78 65 73 3b 20 69 | 2b 2b 2c 20 62 6f 78 70 |boxes; i|++, boxp|
|00002730| 2b 2b 29 20 7b 0a 58 20 | 20 20 20 63 30 20 3d 20 |++) {.X | c0 = |
|00002740| 28 62 6f 78 70 2d 3e 63 | 30 6d 61 78 20 2d 20 62 |(boxp->c|0max - b|
|00002750| 6f 78 70 2d 3e 63 30 6d | 69 6e 29 20 2a 20 59 5f |oxp->c0m|in) * Y_|
|00002760| 53 43 41 4c 45 3b 0a 58 | 20 20 20 20 63 31 20 3d |SCALE;.X| c1 =|
|00002770| 20 28 62 6f 78 70 2d 3e | 63 31 6d 61 78 20 2d 20 | (boxp->|c1max - |
|00002780| 62 6f 78 70 2d 3e 63 31 | 6d 69 6e 29 20 3c 3c 20 |boxp->c1|min) << |
|00002790| 28 48 49 53 54 5f 59 5f | 42 49 54 53 2d 48 49 53 |(HIST_Y_|BITS-HIS|
|000027a0| 54 5f 43 5f 42 49 54 53 | 29 3b 0a 58 20 20 20 20 |T_C_BITS|);.X |
|000027b0| 63 32 20 3d 20 28 62 6f | 78 70 2d 3e 63 32 6d 61 |c2 = (bo|xp->c2ma|
|000027c0| 78 20 2d 20 62 6f 78 70 | 2d 3e 63 32 6d 69 6e 29 |x - boxp|->c2min)|
|000027d0| 20 3c 3c 20 28 48 49 53 | 54 5f 59 5f 42 49 54 53 | << (HIS|T_Y_BITS|
|000027e0| 2d 48 49 53 54 5f 43 5f | 42 49 54 53 29 3b 0a 58 |-HIST_C_|BITS);.X|
|000027f0| 20 20 20 20 6e 6f 72 6d | 20 3d 20 63 30 2a 63 30 | norm| = c0*c0|
|00002800| 20 2b 20 63 31 2a 63 31 | 20 2b 20 63 32 2a 63 32 | + c1*c1| + c2*c2|
|00002810| 3b 0a 58 20 20 20 20 69 | 66 20 28 6e 6f 72 6d 20 |;.X i|f (norm |
|00002820| 3e 20 6d 61 78 29 20 7b | 0a 58 20 20 20 20 20 20 |> max) {|.X |
|00002830| 77 68 69 63 68 20 3d 20 | 62 6f 78 70 3b 0a 58 20 |which = |boxp;.X |
|00002840| 20 20 20 20 20 6d 61 78 | 20 3d 20 6e 6f 72 6d 3b | max| = norm;|
|00002850| 0a 58 20 20 20 20 7d 0a | 58 20 20 7d 0a 58 20 20 |.X }.|X }.X |
|00002860| 72 65 74 75 72 6e 20 77 | 68 69 63 68 3b 0a 58 7d |return w|hich;.X}|
|00002870| 0a 58 0a 58 0a 58 4c 4f | 43 41 4c 20 76 6f 69 64 |.X.X.XLO|CAL void|
|00002880| 0a 58 75 70 64 61 74 65 | 5f 62 6f 78 20 28 62 6f |.Xupdate|_box (bo|
|00002890| 78 70 74 72 20 62 6f 78 | 70 29 0a 58 2f 2a 20 53 |xptr box|p).X/* S|
|000028a0| 68 72 69 6e 6b 20 74 68 | 65 20 6d 69 6e 2f 6d 61 |hrink th|e min/ma|
|000028b0| 78 20 62 6f 75 6e 64 73 | 20 6f 66 20 61 20 62 6f |x bounds| of a bo|
|000028c0| 78 20 74 6f 20 65 6e 63 | 6c 6f 73 65 20 6f 6e 6c |x to enc|lose onl|
|000028d0| 79 20 6e 6f 6e 7a 65 72 | 6f 20 65 6c 65 6d 65 6e |y nonzer|o elemen|
|000028e0| 74 73 2c 20 2a 2f 0a 58 | 2f 2a 20 61 6e 64 20 72 |ts, */.X|/* and r|
|000028f0| 65 63 6f 6d 70 75 74 65 | 20 69 74 73 20 70 6f 70 |ecompute| its pop|
|00002900| 75 6c 61 74 69 6f 6e 20 | 2a 2f 0a 58 7b 0a 58 20 |ulation |*/.X{.X |
|00002910| 20 68 69 73 74 70 74 72 | 20 68 69 73 74 70 3b 0a | histptr| histp;.|
|00002920| 58 20 20 69 6e 74 20 63 | 30 2c 63 31 2c 63 32 3b |X int c|0,c1,c2;|
|00002930| 0a 58 20 20 69 6e 74 20 | 63 30 6d 69 6e 2c 63 30 |.X int |c0min,c0|
|00002940| 6d 61 78 2c 63 31 6d 69 | 6e 2c 63 31 6d 61 78 2c |max,c1mi|n,c1max,|
|00002950| 63 32 6d 69 6e 2c 63 32 | 6d 61 78 3b 0a 58 20 20 |c2min,c2|max;.X |
|00002960| 6c 6f 6e 67 20 63 63 6f | 75 6e 74 3b 0a 58 20 20 |long cco|unt;.X |
|00002970| 0a 58 20 20 63 30 6d 69 | 6e 20 3d 20 62 6f 78 70 |.X c0mi|n = boxp|
|00002980| 2d 3e 63 30 6d 69 6e 3b | 20 20 63 30 6d 61 78 20 |->c0min;| c0max |
|00002990| 3d 20 62 6f 78 70 2d 3e | 63 30 6d 61 78 3b 0a 58 |= boxp->|c0max;.X|
|000029a0| 20 20 63 31 6d 69 6e 20 | 3d 20 62 6f 78 70 2d 3e | c1min |= boxp->|
|000029b0| 63 31 6d 69 6e 3b 20 20 | 63 31 6d 61 78 20 3d 20 |c1min; |c1max = |
|000029c0| 62 6f 78 70 2d 3e 63 31 | 6d 61 78 3b 0a 58 20 20 |boxp->c1|max;.X |
|000029d0| 63 32 6d 69 6e 20 3d 20 | 62 6f 78 70 2d 3e 63 32 |c2min = |boxp->c2|
|000029e0| 6d 69 6e 3b 20 20 63 32 | 6d 61 78 20 3d 20 62 6f |min; c2|max = bo|
|000029f0| 78 70 2d 3e 63 32 6d 61 | 78 3b 0a 58 20 20 0a 58 |xp->c2ma|x;.X .X|
|00002a00| 20 20 69 66 20 28 63 30 | 6d 61 78 20 3e 20 63 30 | if (c0|max > c0|
|00002a10| 6d 69 6e 29 0a 58 20 20 | 20 20 66 6f 72 20 28 63 |min).X | for (c|
|00002a20| 30 20 3d 20 63 30 6d 69 | 6e 3b 20 63 30 20 3c 3d |0 = c0mi|n; c0 <=|
|00002a30| 20 63 30 6d 61 78 3b 20 | 63 30 2b 2b 29 0a 58 20 | c0max; |c0++).X |
|00002a40| 20 20 20 20 20 66 6f 72 | 20 28 63 31 20 3d 20 63 | for| (c1 = c|
|00002a50| 31 6d 69 6e 3b 20 63 31 | 20 3c 3d 20 63 31 6d 61 |1min; c1| <= c1ma|
|00002a60| 78 3b 20 63 31 2b 2b 29 | 20 7b 0a 58 09 68 69 73 |x; c1++)| {.X.his|
|00002a70| 74 70 20 3d 20 26 20 68 | 69 73 74 6f 67 72 61 6d |tp = & h|istogram|
|00002a80| 5b 63 30 5d 5b 63 31 5d | 5b 63 32 6d 69 6e 5d 3b |[c0][c1]|[c2min];|
|00002a90| 0a 58 09 66 6f 72 20 28 | 63 32 20 3d 20 63 32 6d |.X.for (|c2 = c2m|
|00002aa0| 69 6e 3b 20 63 32 20 3c | 3d 20 63 32 6d 61 78 3b |in; c2 <|= c2max;|
|00002ab0| 20 63 32 2b 2b 29 0a 58 | 09 20 20 69 66 20 28 2a | c2++).X|. if (*|
|00002ac0| 68 69 73 74 70 2b 2b 20 | 21 3d 20 30 29 20 7b 0a |histp++ |!= 0) {.|
|00002ad0| 58 09 20 20 20 20 62 6f | 78 70 2d 3e 63 30 6d 69 |X. bo|xp->c0mi|
|00002ae0| 6e 20 3d 20 63 30 6d 69 | 6e 20 3d 20 63 30 3b 0a |n = c0mi|n = c0;.|
|00002af0| 58 09 20 20 20 20 67 6f | 74 6f 20 68 61 76 65 5f |X. go|to have_|
|00002b00| 63 30 6d 69 6e 3b 0a 58 | 09 20 20 7d 0a 58 20 20 |c0min;.X|. }.X |
|00002b10| 20 20 20 20 7d 0a 58 20 | 68 61 76 65 5f 63 30 6d | }.X |have_c0m|
|00002b20| 69 6e 3a 0a 58 20 20 69 | 66 20 28 63 30 6d 61 78 |in:.X i|f (c0max|
|00002b30| 20 3e 20 63 30 6d 69 6e | 29 0a 58 20 20 20 20 66 | > c0min|).X f|
|00002b40| 6f 72 20 28 63 30 20 3d | 20 63 30 6d 61 78 3b 20 |or (c0 =| c0max; |
|00002b50| 63 30 20 3e 3d 20 63 30 | 6d 69 6e 3b 20 63 30 2d |c0 >= c0|min; c0-|
|00002b60| 2d 29 0a 58 20 20 20 20 | 20 20 66 6f 72 20 28 63 |-).X | for (c|
|00002b70| 31 20 3d 20 63 31 6d 69 | 6e 3b 20 63 31 20 3c 3d |1 = c1mi|n; c1 <=|
|00002b80| 20 63 31 6d 61 78 3b 20 | 63 31 2b 2b 29 20 7b 0a | c1max; |c1++) {.|
|00002b90| 58 09 68 69 73 74 70 20 | 3d 20 26 20 68 69 73 74 |X.histp |= & hist|
|00002ba0| 6f 67 72 61 6d 5b 63 30 | 5d 5b 63 31 5d 5b 63 32 |ogram[c0|][c1][c2|
|00002bb0| 6d 69 6e 5d 3b 0a 58 09 | 66 6f 72 20 28 63 32 20 |min];.X.|for (c2 |
|00002bc0| 3d 20 63 32 6d 69 6e 3b | 20 63 32 20 3c 3d 20 63 |= c2min;| c2 <= c|
|00002bd0| 32 6d 61 78 3b 20 63 32 | 2b 2b 29 0a 58 09 20 20 |2max; c2|++).X. |
|00002be0| 69 66 20 28 2a 68 69 73 | 74 70 2b 2b 20 21 3d 20 |if (*his|tp++ != |
|00002bf0| 30 29 20 7b 0a 58 09 20 | 20 20 20 62 6f 78 70 2d |0) {.X. | boxp-|
|00002c00| 3e 63 30 6d 61 78 20 3d | 20 63 30 6d 61 78 20 3d |>c0max =| c0max =|
|00002c10| 20 63 30 3b 0a 58 09 20 | 20 20 20 67 6f 74 6f 20 | c0;.X. | goto |
|00002c20| 68 61 76 65 5f 63 30 6d | 61 78 3b 0a 58 09 20 20 |have_c0m|ax;.X. |
|00002c30| 7d 0a 58 20 20 20 20 20 | 20 7d 0a 58 20 68 61 76 |}.X | }.X hav|
|00002c40| 65 5f 63 30 6d 61 78 3a | 0a 58 20 20 69 66 20 28 |e_c0max:|.X if (|
|00002c50| 63 31 6d 61 78 20 3e 20 | 63 31 6d 69 6e 29 0a 58 |c1max > |c1min).X|
|00002c60| 20 20 20 20 66 6f 72 20 | 28 63 31 20 3d 20 63 31 | for |(c1 = c1|
|00002c70| 6d 69 6e 3b 20 63 31 20 | 3c 3d 20 63 31 6d 61 78 |min; c1 |<= c1max|
|00002c80| 3b 20 63 31 2b 2b 29 0a | 58 20 20 20 20 20 20 66 |; c1++).|X f|
|00002c90| 6f 72 20 28 63 30 20 3d | 20 63 30 6d 69 6e 3b 20 |or (c0 =| c0min; |
|00002ca0| 63 30 20 3c 3d 20 63 30 | 6d 61 78 3b 20 63 30 2b |c0 <= c0|max; c0+|
|00002cb0| 2b 29 20 7b 0a 58 09 68 | 69 73 74 70 20 3d 20 26 |+) {.X.h|istp = &|
|00002cc0| 20 68 69 73 74 6f 67 72 | 61 6d 5b 63 30 5d 5b 63 | histogr|am[c0][c|
|00002cd0| 31 5d 5b 63 32 6d 69 6e | 5d 3b 0a 58 09 66 6f 72 |1][c2min|];.X.for|
|00002ce0| 20 28 63 32 20 3d 20 63 | 32 6d 69 6e 3b 20 63 32 | (c2 = c|2min; c2|
|00002cf0| 20 3c 3d 20 63 32 6d 61 | 78 3b 20 63 32 2b 2b 29 | <= c2ma|x; c2++)|
|00002d00| 0a 58 09 20 20 69 66 20 | 28 2a 68 69 73 74 70 2b |.X. if |(*histp+|
|00002d10| 2b 20 21 3d 20 30 29 20 | 7b 0a 58 09 20 20 20 20 |+ != 0) |{.X. |
|00002d20| 62 6f 78 70 2d 3e 63 31 | 6d 69 6e 20 3d 20 63 31 |boxp->c1|min = c1|
|00002d30| 6d 69 6e 20 3d 20 63 31 | 3b 0a 58 09 20 20 20 20 |min = c1|;.X. |
|00002d40| 67 6f 74 6f 20 68 61 76 | 65 5f 63 31 6d 69 6e 3b |goto hav|e_c1min;|
|00002d50| 0a 58 09 20 20 7d 0a 58 | 20 20 20 20 20 20 7d 0a |.X. }.X| }.|
|00002d60| 58 20 68 61 76 65 5f 63 | 31 6d 69 6e 3a 0a 58 20 |X have_c|1min:.X |
|00002d70| 20 69 66 20 28 63 31 6d | 61 78 20 3e 20 63 31 6d | if (c1m|ax > c1m|
|00002d80| 69 6e 29 0a 58 20 20 20 | 20 66 6f 72 20 28 63 31 |in).X | for (c1|
|00002d90| 20 3d 20 63 31 6d 61 78 | 3b 20 63 31 20 3e 3d 20 | = c1max|; c1 >= |
|00002da0| 63 31 6d 69 6e 3b 20 63 | 31 2d 2d 29 0a 58 20 20 |c1min; c|1--).X |
|00002db0| 20 20 20 20 66 6f 72 20 | 28 63 30 20 3d 20 63 30 | for |(c0 = c0|
|00002dc0| 6d 69 6e 3b 20 63 30 20 | 3c 3d 20 63 30 6d 61 78 |min; c0 |<= c0max|
|00002dd0| 3b 20 63 30 2b 2b 29 20 | 7b 0a 58 09 68 69 73 74 |; c0++) |{.X.hist|
|00002de0| 70 20 3d 20 26 20 68 69 | 73 74 6f 67 72 61 6d 5b |p = & hi|stogram[|
|00002df0| 63 30 5d 5b 63 31 5d 5b | 63 32 6d 69 6e 5d 3b 0a |c0][c1][|c2min];.|
|00002e00| 58 09 66 6f 72 20 28 63 | 32 20 3d 20 63 32 6d 69 |X.for (c|2 = c2mi|
|00002e10| 6e 3b 20 63 32 20 3c 3d | 20 63 32 6d 61 78 3b 20 |n; c2 <=| c2max; |
|00002e20| 63 32 2b 2b 29 0a 58 09 | 20 20 69 66 20 28 2a 68 |c2++).X.| if (*h|
|00002e30| 69 73 74 70 2b 2b 20 21 | 3d 20 30 29 20 7b 0a 58 |istp++ !|= 0) {.X|
|00002e40| 09 20 20 20 20 62 6f 78 | 70 2d 3e 63 31 6d 61 78 |. box|p->c1max|
|00002e50| 20 3d 20 63 31 6d 61 78 | 20 3d 20 63 31 3b 0a 58 | = c1max| = c1;.X|
|00002e60| 09 20 20 20 20 67 6f 74 | 6f 20 68 61 76 65 5f 63 |. got|o have_c|
|00002e70| 31 6d 61 78 3b 0a 58 09 | 20 20 7d 0a 58 20 20 20 |1max;.X.| }.X |
|00002e80| 20 20 20 7d 0a 58 20 68 | 61 76 65 5f 63 31 6d 61 | }.X h|ave_c1ma|
|00002e90| 78 3a 0a 58 20 20 69 66 | 20 28 63 32 6d 61 78 20 |x:.X if| (c2max |
|00002ea0| 3e 20 63 32 6d 69 6e 29 | 0a 58 20 20 20 20 66 6f |> c2min)|.X fo|
|00002eb0| 72 20 28 63 32 20 3d 20 | 63 32 6d 69 6e 3b 20 63 |r (c2 = |c2min; c|
|00002ec0| 32 20 3c 3d 20 63 32 6d | 61 78 3b 20 63 32 2b 2b |2 <= c2m|ax; c2++|
|00002ed0| 29 0a 58 20 20 20 20 20 | 20 66 6f 72 20 28 63 30 |).X | for (c0|
|00002ee0| 20 3d 20 63 30 6d 69 6e | 3b 20 63 30 20 3c 3d 20 | = c0min|; c0 <= |
|00002ef0| 63 30 6d 61 78 3b 20 63 | 30 2b 2b 29 20 7b 0a 58 |c0max; c|0++) {.X|
|00002f00| 09 68 69 73 74 70 20 3d | 20 26 20 68 69 73 74 6f |.histp =| & histo|
|00002f10| 67 72 61 6d 5b 63 30 5d | 5b 63 31 6d 69 6e 5d 5b |gram[c0]|[c1min][|
|00002f20| 63 32 5d 3b 0a 58 09 66 | 6f 72 20 28 63 31 20 3d |c2];.X.f|or (c1 =|
|00002f30| 20 63 31 6d 69 6e 3b 20 | 63 31 20 3c 3d 20 63 31 | c1min; |c1 <= c1|
|00002f40| 6d 61 78 3b 20 63 31 2b | 2b 2c 20 68 69 73 74 70 |max; c1+|+, histp|
|00002f50| 20 2b 3d 20 48 49 53 54 | 5f 43 5f 45 4c 45 4d 53 | += HIST|_C_ELEMS|
|00002f60| 29 0a 58 09 20 20 69 66 | 20 28 2a 68 69 73 74 70 |).X. if| (*histp|
|00002f70| 20 21 3d 20 30 29 20 7b | 0a 58 09 20 20 20 20 62 | != 0) {|.X. b|
|00002f80| 6f 78 70 2d 3e 63 32 6d | 69 6e 20 3d 20 63 32 6d |oxp->c2m|in = c2m|
|00002f90| 69 6e 20 3d 20 63 32 3b | 0a 58 09 20 20 20 20 67 |in = c2;|.X. g|
|00002fa0| 6f 74 6f 20 68 61 76 65 | 5f 63 32 6d 69 6e 3b 0a |oto have|_c2min;.|
|00002fb0| 58 09 20 20 7d 0a 58 20 | 20 20 20 20 20 7d 0a 58 |X. }.X | }.X|
|00002fc0| 20 68 61 76 65 5f 63 32 | 6d 69 6e 3a 0a 58 20 20 | have_c2|min:.X |
|00002fd0| 69 66 20 28 63 32 6d 61 | 78 20 3e 20 63 32 6d 69 |if (c2ma|x > c2mi|
|00002fe0| 6e 29 0a 58 20 20 20 20 | 66 6f 72 20 28 63 32 20 |n).X |for (c2 |
|00002ff0| 3d 20 63 32 6d 61 78 3b | 20 63 32 20 3e 3d 20 63 |= c2max;| c2 >= c|
|00003000| 32 6d 69 6e 3b 20 63 32 | 2d 2d 29 0a 58 20 20 20 |2min; c2|--).X |
|00003010| 20 20 20 66 6f 72 20 28 | 63 30 20 3d 20 63 30 6d | for (|c0 = c0m|
|00003020| 69 6e 3b 20 63 30 20 3c | 3d 20 63 30 6d 61 78 3b |in; c0 <|= c0max;|
|00003030| 20 63 30 2b 2b 29 20 7b | 0a 58 09 68 69 73 74 70 | c0++) {|.X.histp|
|00003040| 20 3d 20 26 20 68 69 73 | 74 6f 67 72 61 6d 5b 63 | = & his|togram[c|
|00003050| 30 5d 5b 63 31 6d 69 6e | 5d 5b 63 32 5d 3b 0a 58 |0][c1min|][c2];.X|
|00003060| 09 66 6f 72 20 28 63 31 | 20 3d 20 63 31 6d 69 6e |.for (c1| = c1min|
|00003070| 3b 20 63 31 20 3c 3d 20 | 63 31 6d 61 78 3b 20 63 |; c1 <= |c1max; c|
|00003080| 31 2b 2b 2c 20 68 69 73 | 74 70 20 2b 3d 20 48 49 |1++, his|tp += HI|
|00003090| 53 54 5f 43 5f 45 4c 45 | 4d 53 29 0a 58 09 20 20 |ST_C_ELE|MS).X. |
|000030a0| 69 66 20 28 2a 68 69 73 | 74 70 20 21 3d 20 30 29 |if (*his|tp != 0)|
|000030b0| 20 7b 0a 58 09 20 20 20 | 20 62 6f 78 70 2d 3e 63 | {.X. | boxp->c|
|000030c0| 32 6d 61 78 20 3d 20 63 | 32 6d 61 78 20 3d 20 63 |2max = c|2max = c|
|000030d0| 32 3b 0a 58 09 20 20 20 | 20 67 6f 74 6f 20 68 61 |2;.X. | goto ha|
|000030e0| 76 65 5f 63 32 6d 61 78 | 3b 0a 58 09 20 20 7d 0a |ve_c2max|;.X. }.|
|000030f0| 58 20 20 20 20 20 20 7d | 0a 58 20 68 61 76 65 5f |X }|.X have_|
|00003100| 63 32 6d 61 78 3a 0a 58 | 20 20 0a 58 20 20 2f 2a |c2max:.X| .X /*|
|00003110| 20 4e 6f 77 20 73 63 61 | 6e 20 72 65 6d 61 69 6e | Now sca|n remain|
|00003120| 69 6e 67 20 76 6f 6c 75 | 6d 65 20 6f 66 20 62 6f |ing volu|me of bo|
|00003130| 78 20 61 6e 64 20 63 6f | 6d 70 75 74 65 20 70 6f |x and co|mpute po|
|00003140| 70 75 6c 61 74 69 6f 6e | 20 2a 2f 0a 58 20 20 63 |pulation| */.X c|
|00003150| 63 6f 75 6e 74 20 3d 20 | 30 3b 0a 58 20 20 66 6f |count = |0;.X fo|
|00003160| 72 20 28 63 30 20 3d 20 | 63 30 6d 69 6e 3b 20 63 |r (c0 = |c0min; c|
|00003170| 30 20 3c 3d 20 63 30 6d | 61 78 3b 20 63 30 2b 2b |0 <= c0m|ax; c0++|
|00003180| 29 0a 58 20 20 20 20 66 | 6f 72 20 28 63 31 20 3d |).X f|or (c1 =|
|00003190| 20 63 31 6d 69 6e 3b 20 | 63 31 20 3c 3d 20 63 31 | c1min; |c1 <= c1|
|000031a0| 6d 61 78 3b 20 63 31 2b | 2b 29 20 7b 0a 58 20 20 |max; c1+|+) {.X |
|000031b0| 20 20 20 20 68 69 73 74 | 70 20 3d 20 26 20 68 69 | hist|p = & hi|
|000031c0| 73 74 6f 67 72 61 6d 5b | 63 30 5d 5b 63 31 5d 5b |stogram[|c0][c1][|
|000031d0| 63 32 6d 69 6e 5d 3b 0a | 58 20 20 20 20 20 20 66 |c2min];.|X f|
|000031e0| 6f 72 20 28 63 32 20 3d | 20 63 32 6d 69 6e 3b 20 |or (c2 =| c2min; |
|000031f0| 63 32 20 3c 3d 20 63 32 | 6d 61 78 3b 20 63 32 2b |c2 <= c2|max; c2+|
|00003200| 2b 2c 20 68 69 73 74 70 | 2b 2b 29 0a 58 09 69 66 |+, histp|++).X.if|
|00003210| 20 28 2a 68 69 73 74 70 | 20 21 3d 20 30 29 20 7b | (*histp| != 0) {|
|00003220| 0a 58 09 20 20 63 63 6f | 75 6e 74 2b 2b 3b 0a 58 |.X. cco|unt++;.X|
|00003230| 09 7d 0a 58 20 20 20 20 | 7d 0a 58 20 20 62 6f 78 |.}.X |}.X box|
|00003240| 70 2d 3e 63 6f 6c 6f 72 | 63 6f 75 6e 74 20 3d 20 |p->color|count = |
|00003250| 63 63 6f 75 6e 74 3b 0a | 58 7d 0a 58 0a 58 0a 58 |ccount;.|X}.X.X.X|
|00003260| 4c 4f 43 41 4c 20 76 6f | 69 64 0a 58 6d 65 64 69 |LOCAL vo|id.Xmedi|
|00003270| 61 6e 5f 63 75 74 20 28 | 69 6e 74 20 64 65 73 69 |an_cut (|int desi|
|00003280| 72 65 64 5f 63 6f 6c 6f | 72 73 29 0a 58 2f 2a 20 |red_colo|rs).X/* |
|00003290| 52 65 70 65 61 74 65 64 | 6c 79 20 73 65 6c 65 63 |Repeated|ly selec|
|000032a0| 74 20 61 6e 64 20 73 70 | 6c 69 74 20 74 68 65 20 |t and sp|lit the |
|000032b0| 6c 61 72 67 65 73 74 20 | 62 6f 78 20 75 6e 74 69 |largest |box unti|
|000032c0| 6c 20 77 65 20 68 61 76 | 65 20 65 6e 6f 75 67 68 |l we hav|e enough|
|000032d0| 20 62 6f 78 65 73 20 2a | 2f 0a 58 7b 0a 58 20 20 | boxes *|/.X{.X |
|000032e0| 69 6e 74 20 6e 2c 6c 62 | 3b 0a 58 20 20 69 6e 74 |int n,lb|;.X int|
|000032f0| 20 63 30 2c 63 31 2c 63 | 32 2c 63 6d 61 78 3b 0a | c0,c1,c|2,cmax;.|
|00003300| 58 20 20 72 65 67 69 73 | 74 65 72 20 62 6f 78 70 |X regis|ter boxp|
|00003310| 74 72 20 62 31 2c 62 32 | 3b 0a 58 0a 58 20 20 77 |tr b1,b2|;.X.X w|
|00003320| 68 69 6c 65 20 28 6e 75 | 6d 62 6f 78 65 73 20 3c |hile (nu|mboxes <|
|00003330| 20 64 65 73 69 72 65 64 | 5f 63 6f 6c 6f 72 73 29 | desired|_colors)|
|00003340| 20 7b 0a 58 20 20 20 20 | 2f 2a 20 53 65 6c 65 63 | {.X |/* Selec|
|00003350| 74 20 62 6f 78 20 74 6f | 20 73 70 6c 69 74 20 2a |t box to| split *|
|00003360| 2f 0a 58 20 20 20 20 2f | 2a 20 43 75 72 72 65 6e |/.X /|* Curren|
|00003370| 74 20 61 6c 67 6f 72 69 | 74 68 6d 3a 20 62 79 20 |t algori|thm: by |
|00003380| 70 6f 70 75 6c 61 74 69 | 6f 6e 20 66 6f 72 20 66 |populati|on for f|
|00003390| 69 72 73 74 20 68 61 6c | 66 2c 20 74 68 65 6e 20 |irst hal|f, then |
|000033a0| 62 79 20 76 6f 6c 75 6d | 65 20 2a 2f 0a 58 20 20 |by volum|e */.X |
|000033b0| 20 20 69 66 20 28 6e 75 | 6d 62 6f 78 65 73 2a 32 | if (nu|mboxes*2|
|000033c0| 20 3c 3d 20 64 65 73 69 | 72 65 64 5f 63 6f 6c 6f | <= desi|red_colo|
|000033d0| 72 73 29 20 7b 0a 58 20 | 20 20 20 20 20 62 31 20 |rs) {.X | b1 |
|000033e0| 3d 20 66 69 6e 64 5f 62 | 69 67 67 65 73 74 5f 63 |= find_b|iggest_c|
|000033f0| 6f 6c 6f 72 5f 70 6f 70 | 28 29 3b 0a 58 20 20 20 |olor_pop|();.X |
|00003400| 20 7d 20 65 6c 73 65 20 | 7b 0a 58 20 20 20 20 20 | } else |{.X |
|00003410| 20 62 31 20 3d 20 66 69 | 6e 64 5f 62 69 67 67 65 | b1 = fi|nd_bigge|
|00003420| 73 74 5f 76 6f 6c 75 6d | 65 28 29 3b 0a 58 20 20 |st_volum|e();.X |
|00003430| 20 20 7d 0a 58 20 20 20 | 20 69 66 20 28 62 31 20 | }.X | if (b1 |
|00003440| 3d 3d 20 4e 55 4c 4c 29 | 09 09 2f 2a 20 6e 6f 20 |== NULL)|../* no |
|00003450| 73 70 6c 69 74 74 61 62 | 6c 65 20 62 6f 78 65 73 |splittab|le boxes|
|00003460| 20 6c 65 66 74 21 20 2a | 2f 0a 58 20 20 20 20 20 | left! *|/.X |
|00003470| 20 62 72 65 61 6b 3b 0a | 58 20 20 20 20 62 32 20 | break;.|X b2 |
|00003480| 3d 20 26 62 6f 78 6c 69 | 73 74 5b 6e 75 6d 62 6f |= &boxli|st[numbo|
|00003490| 78 65 73 5d 3b 09 2f 2a | 20 77 68 65 72 65 20 6e |xes];./*| where n|
|000034a0| 65 77 20 62 6f 78 20 77 | 69 6c 6c 20 67 6f 20 2a |ew box w|ill go *|
|000034b0| 2f 0a 58 20 20 20 20 2f | 2a 20 43 6f 70 79 20 74 |/.X /|* Copy t|
|000034c0| 68 65 20 63 6f 6c 6f 72 | 20 62 6f 75 6e 64 73 20 |he color| bounds |
|000034d0| 74 6f 20 74 68 65 20 6e | 65 77 20 62 6f 78 2e 20 |to the n|ew box. |
|000034e0| 2a 2f 0a 58 20 20 20 20 | 62 32 2d 3e 63 30 6d 61 |*/.X |b2->c0ma|
|000034f0| 78 20 3d 20 62 31 2d 3e | 63 30 6d 61 78 3b 20 62 |x = b1->|c0max; b|
|00003500| 32 2d 3e 63 31 6d 61 78 | 20 3d 20 62 31 2d 3e 63 |2->c1max| = b1->c|
|00003510| 31 6d 61 78 3b 20 62 32 | 2d 3e 63 32 6d 61 78 20 |1max; b2|->c2max |
|00003520| 3d 20 62 31 2d 3e 63 32 | 6d 61 78 3b 0a 58 20 20 |= b1->c2|max;.X |
|00003530| 20 20 62 32 2d 3e 63 30 | 6d 69 6e 20 3d 20 62 31 | b2->c0|min = b1|
|00003540| 2d 3e 63 30 6d 69 6e 3b | 20 62 32 2d 3e 63 31 6d |->c0min;| b2->c1m|
|00003550| 69 6e 20 3d 20 62 31 2d | 3e 63 31 6d 69 6e 3b 20 |in = b1-|>c1min; |
|00003560| 62 32 2d 3e 63 32 6d 69 | 6e 20 3d 20 62 31 2d 3e |b2->c2mi|n = b1->|
|00003570| 63 32 6d 69 6e 3b 0a 58 | 20 20 20 20 2f 2a 20 43 |c2min;.X| /* C|
|00003580| 68 6f 6f 73 65 20 77 68 | 69 63 68 20 61 78 69 73 |hoose wh|ich axis|
|00003590| 20 74 6f 20 73 70 6c 69 | 74 20 74 68 65 20 62 6f | to spli|t the bo|
|000035a0| 78 20 6f 6e 2e 0a 58 20 | 20 20 20 20 2a 20 43 75 |x on..X | * Cu|
|000035b0| 72 72 65 6e 74 20 61 6c | 67 6f 72 69 74 68 6d 3a |rrent al|gorithm:|
|000035c0| 20 6c 6f 6e 67 65 73 74 | 20 73 63 61 6c 65 64 20 | longest| scaled |
|000035d0| 61 78 69 73 2e 0a 58 20 | 20 20 20 20 2a 20 53 65 |axis..X | * Se|
|000035e0| 65 20 6e 6f 74 65 73 20 | 69 6e 20 66 69 6e 64 5f |e notes |in find_|
|000035f0| 62 69 67 67 65 73 74 5f | 76 6f 6c 75 6d 65 20 61 |biggest_|volume a|
|00003600| 62 6f 75 74 20 73 63 61 | 6c 69 6e 67 2e 2e 2e 0a |bout sca|ling....|
|00003610| 58 20 20 20 20 20 2a 2f | 0a 58 20 20 20 20 63 30 |X */|.X c0|
|00003620| 20 3d 20 28 62 31 2d 3e | 63 30 6d 61 78 20 2d 20 | = (b1->|c0max - |
|00003630| 62 31 2d 3e 63 30 6d 69 | 6e 29 20 2a 20 59 5f 53 |b1->c0mi|n) * Y_S|
|00003640| 43 41 4c 45 3b 0a 58 20 | 20 20 20 63 31 20 3d 20 |CALE;.X | c1 = |
|00003650| 28 62 31 2d 3e 63 31 6d | 61 78 20 2d 20 62 31 2d |(b1->c1m|ax - b1-|
|00003660| 3e 63 31 6d 69 6e 29 20 | 3c 3c 20 28 48 49 53 54 |>c1min) |<< (HIST|
|00003670| 5f 59 5f 42 49 54 53 2d | 48 49 53 54 5f 43 5f 42 |_Y_BITS-|HIST_C_B|
|00003680| 49 54 53 29 3b 0a 58 20 | 20 20 20 63 32 20 3d 20 |ITS);.X | c2 = |
|00003690| 28 62 31 2d 3e 63 32 6d | 61 78 20 2d 20 62 31 2d |(b1->c2m|ax - b1-|
|000036a0| 3e 63 32 6d 69 6e 29 20 | 3c 3c 20 28 48 49 53 54 |>c2min) |<< (HIST|
|000036b0| 5f 59 5f 42 49 54 53 2d | 48 49 53 54 5f 43 5f 42 |_Y_BITS-|HIST_C_B|
|000036c0| 49 54 53 29 3b 0a 58 20 | 20 20 20 63 6d 61 78 20 |ITS);.X | cmax |
|000036d0| 3d 20 63 30 3b 20 6e 20 | 3d 20 30 3b 0a 58 20 20 |= c0; n |= 0;.X |
|000036e0| 20 20 69 66 20 28 63 31 | 20 3e 20 63 6d 61 78 29 | if (c1| > cmax)|
|000036f0| 20 7b 20 63 6d 61 78 20 | 3d 20 63 31 3b 20 6e 20 | { cmax |= c1; n |
|00003700| 3d 20 31 3b 20 7d 0a 58 | 20 20 20 20 69 66 20 28 |= 1; }.X| if (|
|00003710| 63 32 20 3e 20 63 6d 61 | 78 29 20 7b 20 6e 20 3d |c2 > cma|x) { n =|
|00003720| 20 32 3b 20 7d 0a 58 20 | 20 20 20 2f 2a 20 43 68 | 2; }.X | /* Ch|
|00003730| 6f 6f 73 65 20 73 70 6c | 69 74 20 70 6f 69 6e 74 |oose spl|it point|
|00003740| 20 61 6c 6f 6e 67 20 73 | 65 6c 65 63 74 65 64 20 | along s|elected |
|00003750| 61 78 69 73 2c 20 61 6e | 64 20 75 70 64 61 74 65 |axis, an|d update|
|00003760| 20 62 6f 78 20 62 6f 75 | 6e 64 73 2e 0a 58 20 20 | box bou|nds..X |
|00003770| 20 20 20 2a 20 43 75 72 | 72 65 6e 74 20 61 6c 67 | * Cur|rent alg|
|00003780| 6f 72 69 74 68 6d 3a 20 | 73 70 6c 69 74 20 61 74 |orithm: |split at|
|00003790| 20 68 61 6c 66 77 61 79 | 20 70 6f 69 6e 74 2e 0a | halfway| point..|
|000037a0| 58 20 20 20 20 20 2a 20 | 28 53 69 6e 63 65 20 74 |X * |(Since t|
|000037b0| 68 65 20 62 6f 78 20 68 | 61 73 20 62 65 65 6e 20 |he box h|as been |
|000037c0| 73 68 72 75 6e 6b 20 74 | 6f 20 6d 69 6e 69 6d 75 |shrunk t|o minimu|
|000037d0| 6d 20 76 6f 6c 75 6d 65 | 2c 0a 58 20 20 20 20 20 |m volume|,.X |
|000037e0| 2a 20 61 6e 79 20 73 70 | 6c 69 74 20 77 69 6c 6c |* any sp|lit will|
|000037f0| 20 70 72 6f 64 75 63 65 | 20 74 77 6f 20 6e 6f 6e | produce| two non|
|00003800| 65 6d 70 74 79 20 73 75 | 62 62 6f 78 65 73 2e 29 |empty su|bboxes.)|
|00003810| 0a 58 20 20 20 20 20 2a | 20 4e 6f 74 65 20 74 68 |.X *| Note th|
|00003820| 61 74 20 6c 62 20 76 61 | 6c 75 65 20 69 73 20 6d |at lb va|lue is m|
|00003830| 61 78 20 66 6f 72 20 6c | 6f 77 65 72 20 62 6f 78 |ax for l|ower box|
|00003840| 2c 20 73 6f 20 6d 75 73 | 74 20 62 65 20 3c 20 6f |, so mus|t be < o|
|00003850| 6c 64 20 6d 61 78 2e 0a | 58 20 20 20 20 20 2a 2f |ld max..|X */|
|00003860| 0a 58 20 20 20 20 73 77 | 69 74 63 68 20 28 6e 29 |.X sw|itch (n)|
|00003870| 20 7b 0a 58 20 20 20 20 | 63 61 73 65 20 30 3a 0a | {.X |case 0:.|
|00003880| 58 20 20 20 20 20 20 6c | 62 20 3d 20 28 62 31 2d |X l|b = (b1-|
|00003890| 3e 63 30 6d 61 78 20 2b | 20 62 31 2d 3e 63 30 6d |>c0max +| b1->c0m|
|000038a0| 69 6e 29 20 2f 20 32 3b | 0a 58 20 20 20 20 20 20 |in) / 2;|.X |
|000038b0| 62 31 2d 3e 63 30 6d 61 | 78 20 3d 20 6c 62 3b 0a |b1->c0ma|x = lb;.|
|000038c0| 58 20 20 20 20 20 20 62 | 32 2d 3e 63 30 6d 69 6e |X b|2->c0min|
|000038d0| 20 3d 20 6c 62 2b 31 3b | 0a 58 20 20 20 20 20 20 | = lb+1;|.X |
|000038e0| 62 72 65 61 6b 3b 0a 58 | 20 20 20 20 63 61 73 65 |break;.X| case|
|000038f0| 20 31 3a 0a 58 20 20 20 | 20 20 20 6c 62 20 3d 20 | 1:.X | lb = |
|00003900| 28 62 31 2d 3e 63 31 6d | 61 78 20 2b 20 62 31 2d |(b1->c1m|ax + b1-|
|00003910| 3e 63 31 6d 69 6e 29 20 | 2f 20 32 3b 0a 58 20 20 |>c1min) |/ 2;.X |
|00003920| 20 20 20 20 62 31 2d 3e | 63 31 6d 61 78 20 3d 20 | b1->|c1max = |
|00003930| 6c 62 3b 0a 58 20 20 20 | 20 20 20 62 32 2d 3e 63 |lb;.X | b2->c|
|00003940| 31 6d 69 6e 20 3d 20 6c | 62 2b 31 3b 0a 58 20 20 |1min = l|b+1;.X |
|00003950| 20 20 20 20 62 72 65 61 | 6b 3b 0a 58 20 20 20 20 | brea|k;.X |
|00003960| 63 61 73 65 20 32 3a 0a | 58 20 20 20 20 20 20 6c |case 2:.|X l|
|00003970| 62 20 3d 20 28 62 31 2d | 3e 63 32 6d 61 78 20 2b |b = (b1-|>c2max +|
|00003980| 20 62 31 2d 3e 63 32 6d | 69 6e 29 20 2f 20 32 3b | b1->c2m|in) / 2;|
|00003990| 0a 58 20 20 20 20 20 20 | 62 31 2d 3e 63 32 6d 61 |.X |b1->c2ma|
|000039a0| 78 20 3d 20 6c 62 3b 0a | 58 20 20 20 20 20 20 62 |x = lb;.|X b|
|000039b0| 32 2d 3e 63 32 6d 69 6e | 20 3d 20 6c 62 2b 31 3b |2->c2min| = lb+1;|
|000039c0| 0a 58 20 20 20 20 20 20 | 62 72 65 61 6b 3b 0a 58 |.X |break;.X|
|000039d0| 20 20 20 20 7d 0a 58 20 | 20 20 20 2f 2a 20 55 70 | }.X | /* Up|
|000039e0| 64 61 74 65 20 73 74 61 | 74 73 20 66 6f 72 20 62 |date sta|ts for b|
|000039f0| 6f 78 65 73 20 2a 2f 0a | 58 20 20 20 20 75 70 64 |oxes */.|X upd|
|00003a00| 61 74 65 5f 62 6f 78 28 | 62 31 29 3b 0a 58 20 20 |ate_box(|b1);.X |
|00003a10| 20 20 75 70 64 61 74 65 | 5f 62 6f 78 28 62 32 29 | update|_box(b2)|
|00003a20| 3b 0a 58 20 20 20 20 6e | 75 6d 62 6f 78 65 73 2b |;.X n|umboxes+|
|00003a30| 2b 3b 0a 58 20 20 7d 0a | 58 7d 0a 58 0a 58 0a 58 |+;.X }.|X}.X.X.X|
|00003a40| 4c 4f 43 41 4c 20 76 6f | 69 64 0a 58 63 6f 6d 70 |LOCAL vo|id.Xcomp|
|00003a50| 75 74 65 5f 63 6f 6c 6f | 72 20 28 62 6f 78 70 74 |ute_colo|r (boxpt|
|00003a60| 72 20 62 6f 78 70 2c 20 | 69 6e 74 20 69 63 6f 6c |r boxp, |int icol|
|00003a70| 6f 72 29 0a 58 2f 2a 20 | 43 6f 6d 70 75 74 65 20 |or).X/* |Compute |
|00003a80| 72 65 70 72 65 73 65 6e | 74 61 74 69 76 65 20 63 |represen|tative c|
|00003a90| 6f 6c 6f 72 20 66 6f 72 | 20 61 20 62 6f 78 2c 20 |olor for| a box, |
|00003aa0| 70 75 74 20 69 74 20 69 | 6e 20 6d 79 5f 63 6f 6c |put it i|n my_col|
|00003ab0| 6f 72 6d 61 70 5b 69 63 | 6f 6c 6f 72 5d 20 2a 2f |ormap[ic|olor] */|
|00003ac0| 0a 58 7b 0a 58 20 20 2f | 2a 20 43 75 72 72 65 6e |.X{.X /|* Curren|
|00003ad0| 74 20 61 6c 67 6f 72 69 | 74 68 6d 3a 20 6d 65 61 |t algori|thm: mea|
|00003ae0| 6e 20 77 65 69 67 68 74 | 65 64 20 62 79 20 70 69 |n weight|ed by pi|
|00003af0| 78 65 6c 73 20 28 6e 6f | 74 20 63 6f 6c 6f 72 73 |xels (no|t colors|
|00003b00| 29 20 2a 2f 0a 58 20 20 | 2f 2a 20 4e 6f 74 65 20 |) */.X |/* Note |
|00003b10| 69 74 20 69 73 20 69 6d | 70 6f 72 74 61 6e 74 20 |it is im|portant |
|00003b20| 74 6f 20 67 65 74 20 74 | 68 65 20 72 6f 75 6e 64 |to get t|he round|
|00003b30| 69 6e 67 20 63 6f 72 72 | 65 63 74 21 20 2a 2f 0a |ing corr|ect! */.|
|00003b40| 58 20 20 68 69 73 74 70 | 74 72 20 68 69 73 74 70 |X histp|tr histp|
|00003b50| 3b 0a 58 20 20 69 6e 74 | 20 63 30 2c 63 31 2c 63 |;.X int| c0,c1,c|
|00003b60| 32 3b 0a 58 20 20 69 6e | 74 20 63 30 6d 69 6e 2c |2;.X in|t c0min,|
|00003b70| 63 30 6d 61 78 2c 63 31 | 6d 69 6e 2c 63 31 6d 61 |c0max,c1|min,c1ma|
|00003b80| 78 2c 63 32 6d 69 6e 2c | 63 32 6d 61 78 3b 0a 58 |x,c2min,|c2max;.X|
|00003b90| 20 20 6c 6f 6e 67 20 63 | 6f 75 6e 74 3b 0a 58 20 | long c|ount;.X |
|00003ba0| 20 6c 6f 6e 67 20 74 6f | 74 61 6c 20 3d 20 30 3b | long to|tal = 0;|
|00003bb0| 0a 58 20 20 6c 6f 6e 67 | 20 63 30 74 6f 74 61 6c |.X long| c0total|
|00003bc0| 20 3d 20 30 3b 0a 58 20 | 20 6c 6f 6e 67 20 63 31 | = 0;.X | long c1|
|00003bd0| 74 6f 74 61 6c 20 3d 20 | 30 3b 0a 58 20 20 6c 6f |total = |0;.X lo|
|00003be0| 6e 67 20 63 32 74 6f 74 | 61 6c 20 3d 20 30 3b 0a |ng c2tot|al = 0;.|
|00003bf0| 58 20 20 0a 58 20 20 63 | 30 6d 69 6e 20 3d 20 62 |X .X c|0min = b|
|00003c00| 6f 78 70 2d 3e 63 30 6d | 69 6e 3b 20 20 63 30 6d |oxp->c0m|in; c0m|
|00003c10| 61 78 20 3d 20 62 6f 78 | 70 2d 3e 63 30 6d 61 78 |ax = box|p->c0max|
|00003c20| 3b 0a 58 20 20 63 31 6d | 69 6e 20 3d 20 62 6f 78 |;.X c1m|in = box|
|00003c30| 70 2d 3e 63 31 6d 69 6e | 3b 20 20 63 31 6d 61 78 |p->c1min|; c1max|
|00003c40| 20 3d 20 62 6f 78 70 2d | 3e 63 31 6d 61 78 3b 0a | = boxp-|>c1max;.|
|00003c50| 58 20 20 63 32 6d 69 6e | 20 3d 20 62 6f 78 70 2d |X c2min| = boxp-|
|00003c60| 3e 63 32 6d 69 6e 3b 20 | 20 63 32 6d 61 78 20 3d |>c2min; | c2max =|
|00003c70| 20 62 6f 78 70 2d 3e 63 | 32 6d 61 78 3b 0a 58 20 | boxp->c|2max;.X |
|00003c80| 20 0a 58 20 20 66 6f 72 | 20 28 63 30 20 3d 20 63 | .X for| (c0 = c|
|00003c90| 30 6d 69 6e 3b 20 63 30 | 20 3c 3d 20 63 30 6d 61 |0min; c0| <= c0ma|
|00003ca0| 78 3b 20 63 30 2b 2b 29 | 0a 58 20 20 20 20 66 6f |x; c0++)|.X fo|
|00003cb0| 72 20 28 63 31 20 3d 20 | 63 31 6d 69 6e 3b 20 63 |r (c1 = |c1min; c|
|00003cc0| 31 20 3c 3d 20 63 31 6d | 61 78 3b 20 63 31 2b 2b |1 <= c1m|ax; c1++|
|00003cd0| 29 20 7b 0a 58 20 20 20 | 20 20 20 68 69 73 74 70 |) {.X | histp|
|00003ce0| 20 3d 20 26 20 68 69 73 | 74 6f 67 72 61 6d 5b 63 | = & his|togram[c|
|00003cf0| 30 5d 5b 63 31 5d 5b 63 | 32 6d 69 6e 5d 3b 0a 58 |0][c1][c|2min];.X|
|00003d00| 20 20 20 20 20 20 66 6f | 72 20 28 63 32 20 3d 20 | fo|r (c2 = |
|00003d10| 63 32 6d 69 6e 3b 20 63 | 32 20 3c 3d 20 63 32 6d |c2min; c|2 <= c2m|
|00003d20| 61 78 3b 20 63 32 2b 2b | 29 20 7b 0a 58 09 69 66 |ax; c2++|) {.X.if|
|00003d30| 20 28 28 63 6f 75 6e 74 | 20 3d 20 2a 68 69 73 74 | ((count| = *hist|
|00003d40| 70 2b 2b 29 20 21 3d 20 | 30 29 20 7b 0a 58 09 20 |p++) != |0) {.X. |
|00003d50| 20 74 6f 74 61 6c 20 2b | 3d 20 63 6f 75 6e 74 3b | total +|= count;|
|00003d60| 0a 58 09 20 20 63 30 74 | 6f 74 61 6c 20 2b 3d 20 |.X. c0t|otal += |
|00003d70| 28 28 63 30 20 3c 3c 20 | 59 5f 53 48 49 46 54 29 |((c0 << |Y_SHIFT)|
|00003d80| 20 2b 20 28 28 31 3c 3c | 59 5f 53 48 49 46 54 29 | + ((1<<|Y_SHIFT)|
|00003d90| 3e 3e 31 29 29 20 2a 20 | 63 6f 75 6e 74 3b 0a 58 |>>1)) * |count;.X|
|00003da0| 09 20 20 63 31 74 6f 74 | 61 6c 20 2b 3d 20 28 28 |. c1tot|al += ((|
|00003db0| 63 31 20 3c 3c 20 43 5f | 53 48 49 46 54 29 20 2b |c1 << C_|SHIFT) +|
|00003dc0| 20 28 28 31 3c 3c 43 5f | 53 48 49 46 54 29 3e 3e | ((1<<C_|SHIFT)>>|
|00003dd0| 31 29 29 20 2a 20 63 6f | 75 6e 74 3b 0a 58 09 20 |1)) * co|unt;.X. |
|00003de0| 20 63 32 74 6f 74 61 6c | 20 2b 3d 20 28 28 63 32 | c2total| += ((c2|
|00003df0| 20 3c 3c 20 43 5f 53 48 | 49 46 54 29 20 2b 20 28 | << C_SH|IFT) + (|
|00003e00| 28 31 3c 3c 43 5f 53 48 | 49 46 54 29 3e 3e 31 29 |(1<<C_SH|IFT)>>1)|
|00003e10| 29 20 2a 20 63 6f 75 6e | 74 3b 0a 58 09 7d 0a 58 |) * coun|t;.X.}.X|
|00003e20| 20 20 20 20 20 20 7d 0a | 58 20 20 20 20 7d 0a 58 | }.|X }.X|
|00003e30| 20 20 0a 58 20 20 6d 79 | 5f 63 6f 6c 6f 72 6d 61 | .X my|_colorma|
|00003e40| 70 5b 30 5d 5b 69 63 6f | 6c 6f 72 5d 20 3d 20 28 |p[0][ico|lor] = (|
|00003e50| 4a 53 41 4d 50 4c 45 29 | 20 28 28 63 30 74 6f 74 |JSAMPLE)| ((c0tot|
|00003e60| 61 6c 20 2b 20 28 74 6f | 74 61 6c 3e 3e 31 29 29 |al + (to|tal>>1))|
|00003e70| 20 2f 20 74 6f 74 61 6c | 29 3b 0a 58 20 20 6d 79 | / total|);.X my|
|00003e80| 5f 63 6f 6c 6f 72 6d 61 | 70 5b 31 5d 5b 69 63 6f |_colorma|p[1][ico|
|00003e90| 6c 6f 72 5d 20 3d 20 28 | 4a 53 41 4d 50 4c 45 29 |lor] = (|JSAMPLE)|
|00003ea0| 20 28 28 63 31 74 6f 74 | 61 6c 20 2b 20 28 74 6f | ((c1tot|al + (to|
|00003eb0| 74 61 6c 3e 3e 31 29 29 | 20 2f 20 74 6f 74 61 6c |tal>>1))| / total|
|00003ec0| 29 3b 0a 58 20 20 6d 79 | 5f 63 6f 6c 6f 72 6d 61 |);.X my|_colorma|
|00003ed0| 70 5b 32 5d 5b 69 63 6f | 6c 6f 72 5d 20 3d 20 28 |p[2][ico|lor] = (|
|00003ee0| 4a 53 41 4d 50 4c 45 29 | 20 28 28 63 32 74 6f 74 |JSAMPLE)| ((c2tot|
|00003ef0| 61 6c 20 2b 20 28 74 6f | 74 61 6c 3e 3e 31 29 29 |al + (to|tal>>1))|
|00003f00| 20 2f 20 74 6f 74 61 6c | 29 3b 0a 58 7d 0a 58 0a | / total|);.X}.X.|
|00003f10| 58 0a 58 4c 4f 43 41 4c | 20 76 6f 69 64 0a 58 72 |X.XLOCAL| void.Xr|
|00003f20| 65 6d 61 70 5f 63 6f 6c | 6f 72 6d 61 70 20 28 64 |emap_col|ormap (d|
|00003f30| 65 63 6f 6d 70 72 65 73 | 73 5f 69 6e 66 6f 5f 70 |ecompres|s_info_p|
|00003f40| 74 72 20 63 69 6e 66 6f | 29 0a 58 2f 2a 20 52 65 |tr cinfo|).X/* Re|
|00003f50| 6d 61 70 20 74 68 65 20 | 69 6e 74 65 72 6e 61 6c |map the |internal|
|00003f60| 20 63 6f 6c 6f 72 6d 61 | 70 20 74 6f 20 74 68 65 | colorma|p to the|
|00003f70| 20 6f 75 74 70 75 74 20 | 63 6f 6c 6f 72 73 70 61 | output |colorspa|
|00003f80| 63 65 20 2a 2f 0a 58 7b | 0a 58 20 20 2f 2a 20 54 |ce */.X{|.X /* T|
|00003f90| 68 69 73 20 72 65 71 75 | 69 72 65 73 20 61 20 6c |his requ|ires a l|
|00003fa0| 69 74 74 6c 65 20 74 72 | 69 63 6b 65 72 79 20 73 |ittle tr|ickery s|
|00003fb0| 69 6e 63 65 20 63 6f 6c | 6f 72 5f 63 6f 6e 76 65 |ince col|or_conve|
|00003fc0| 72 74 20 65 78 70 65 63 | 74 73 20 74 6f 0a 58 20 |rt expec|ts to.X |
|00003fd0| 20 20 2a 20 64 65 61 6c | 20 77 69 74 68 20 33 2d | * deal| with 3-|
|00003fe0| 44 20 61 72 72 61 79 73 | 20 28 61 20 32 2d 44 20 |D arrays| (a 2-D |
|00003ff0| 73 61 6d 70 6c 65 20 61 | 72 72 61 79 20 66 6f 72 |sample a|rray for|
|00004000| 20 65 61 63 68 20 63 6f | 6d 70 6f 6e 65 6e 74 29 | each co|mponent)|
|00004010| 2e 0a 58 20 20 20 2a 20 | 57 65 20 6d 75 73 74 20 |..X * |We must |
|00004020| 70 72 6f 6d 6f 74 65 20 | 74 68 65 20 63 6f 6c 6f |promote |the colo|
|00004030| 72 6d 61 70 73 20 69 6e | 74 6f 20 6f 6e 65 2d 72 |rmaps in|to one-r|
|00004040| 6f 77 20 33 2d 44 20 61 | 72 72 61 79 73 2e 0a 58 |ow 3-D a|rrays..X|
|00004050| 20 20 20 2a 2f 0a 58 20 | 20 73 68 6f 72 74 20 63 | */.X | short c|
|00004060| 69 3b 0a 58 20 20 4a 53 | 41 4d 50 41 52 52 41 59 |i;.X JS|AMPARRAY|
|00004070| 20 69 6e 70 75 74 5f 68 | 61 63 6b 5b 33 5d 3b 0a | input_h|ack[3];.|
|00004080| 58 20 20 4a 53 41 4d 50 | 41 52 52 41 59 20 6f 75 |X JSAMP|ARRAY ou|
|00004090| 74 70 75 74 5f 68 61 63 | 6b 5b 31 30 5d 3b 09 2f |tput_hac|k[10];./|
|000040a0| 2a 20 61 73 73 75 6d 65 | 20 6e 6f 20 6d 6f 72 65 |* assume| no more|
|000040b0| 20 74 68 61 6e 20 31 30 | 20 6f 75 74 70 75 74 20 | than 10| output |
|000040c0| 63 6f 6d 70 6f 6e 65 6e | 74 73 20 2a 2f 0a 58 0a |componen|ts */.X.|
|000040d0| 58 20 20 66 6f 72 20 28 | 63 69 20 3d 20 30 3b 20 |X for (|ci = 0; |
|000040e0| 63 69 20 3c 20 33 3b 20 | 63 69 2b 2b 29 0a 58 20 |ci < 3; |ci++).X |
|000040f0| 20 20 20 69 6e 70 75 74 | 5f 68 61 63 6b 5b 63 69 | input|_hack[ci|
|00004100| 5d 20 3d 20 26 28 6d 79 | 5f 63 6f 6c 6f 72 6d 61 |] = &(my|_colorma|
|00004110| 70 5b 63 69 5d 29 3b 0a | 58 20 20 66 6f 72 20 28 |p[ci]);.|X for (|
|00004120| 63 69 20 3d 20 30 3b 20 | 63 69 20 3c 20 63 69 6e |ci = 0; |ci < cin|
|00004130| 66 6f 2d 3e 63 6f 6c 6f | 72 5f 6f 75 74 5f 63 6f |fo->colo|r_out_co|
|00004140| 6d 70 73 3b 20 63 69 2b | 2b 29 0a 58 20 20 20 20 |mps; ci+|+).X |
|00004150| 6f 75 74 70 75 74 5f 68 | 61 63 6b 5b 63 69 5d 20 |output_h|ack[ci] |
|00004160| 3d 20 26 28 63 69 6e 66 | 6f 2d 3e 63 6f 6c 6f 72 |= &(cinf|o->color|
|00004170| 6d 61 70 5b 63 69 5d 29 | 3b 0a 58 0a 58 20 20 28 |map[ci])|;.X.X (|
|00004180| 2a 63 69 6e 66 6f 2d 3e | 6d 65 74 68 6f 64 73 2d |*cinfo->|methods-|
|00004190| 3e 63 6f 6c 6f 72 5f 63 | 6f 6e 76 65 72 74 29 20 |>color_c|onvert) |
|000041a0| 28 63 69 6e 66 6f 2c 20 | 31 2c 0a 58 09 09 09 09 |(cinfo, |1,.X....|
|000041b0| 20 20 20 20 28 6c 6f 6e | 67 29 20 63 69 6e 66 6f | (lon|g) cinfo|
|000041c0| 2d 3e 61 63 74 75 61 6c | 5f 6e 75 6d 62 65 72 5f |->actual|_number_|
|000041d0| 6f 66 5f 63 6f 6c 6f 72 | 73 2c 0a 58 09 09 09 09 |of_color|s,.X....|
|000041e0| 20 20 20 20 69 6e 70 75 | 74 5f 68 61 63 6b 2c 20 | inpu|t_hack, |
|000041f0| 6f 75 74 70 75 74 5f 68 | 61 63 6b 29 3b 0a 58 7d |output_h|ack);.X}|
|00004200| 0a 58 0a 58 0a 58 4c 4f | 43 41 4c 20 76 6f 69 64 |.X.X.XLO|CAL void|
|00004210| 0a 58 73 65 6c 65 63 74 | 5f 63 6f 6c 6f 72 73 20 |.Xselect|_colors |
|00004220| 28 64 65 63 6f 6d 70 72 | 65 73 73 5f 69 6e 66 6f |(decompr|ess_info|
|00004230| 5f 70 74 72 20 63 69 6e | 66 6f 29 0a 58 2f 2a 20 |_ptr cin|fo).X/* |
|00004240| 4d 61 73 74 65 72 20 72 | 6f 75 74 69 6e 65 20 66 |Master r|outine f|
|00004250| 6f 72 20 63 6f 6c 6f 72 | 20 73 65 6c 65 63 74 69 |or color| selecti|
|00004260| 6f 6e 20 2a 2f 0a 58 7b | 0a 58 20 20 69 6e 74 20 |on */.X{|.X int |
|00004270| 64 65 73 69 72 65 64 20 | 3d 20 63 69 6e 66 6f 2d |desired |= cinfo-|
|00004280| 3e 64 65 73 69 72 65 64 | 5f 6e 75 6d 62 65 72 5f |>desired|_number_|
|00004290| 6f 66 5f 63 6f 6c 6f 72 | 73 3b 0a 58 20 20 69 6e |of_color|s;.X in|
|000042a0| 74 20 69 3b 0a 58 0a 58 | 20 20 2f 2a 20 41 6c 6c |t i;.X.X| /* All|
|000042b0| 6f 63 61 74 65 20 77 6f | 72 6b 73 70 61 63 65 20 |ocate wo|rkspace |
|000042c0| 66 6f 72 20 62 6f 78 20 | 6c 69 73 74 20 2a 2f 0a |for box |list */.|
|000042d0| 58 20 20 62 6f 78 6c 69 | 73 74 20 3d 20 28 62 6f |X boxli|st = (bo|
|000042e0| 78 70 74 72 29 20 28 2a | 63 69 6e 66 6f 2d 3e 65 |xptr) (*|cinfo->e|
|000042f0| 6d 65 74 68 6f 64 73 2d | 3e 61 6c 6c 6f 63 5f 73 |methods-|>alloc_s|
|00004300| 6d 61 6c 6c 29 20 28 64 | 65 73 69 72 65 64 20 2a |mall) (d|esired *|
|00004310| 20 53 49 5a 45 4f 46 28 | 62 6f 78 29 29 3b 0a 58 | SIZEOF(|box));.X|
|00004320| 20 20 2f 2a 20 49 6e 69 | 74 69 61 6c 69 7a 65 20 | /* Ini|tialize |
|00004330| 6f 6e 65 20 62 6f 78 20 | 63 6f 6e 74 61 69 6e 69 |one box |containi|
|00004340| 6e 67 20 77 68 6f 6c 65 | 20 73 70 61 63 65 20 2a |ng whole| space *|
|00004350| 2f 0a 58 20 20 6e 75 6d | 62 6f 78 65 73 20 3d 20 |/.X num|boxes = |
|00004360| 31 3b 0a 58 20 20 62 6f | 78 6c 69 73 74 5b 30 5d |1;.X bo|xlist[0]|
|00004370| 2e 63 30 6d 69 6e 20 3d | 20 30 3b 0a 58 20 20 62 |.c0min =| 0;.X b|
|00004380| 6f 78 6c 69 73 74 5b 30 | 5d 2e 63 30 6d 61 78 20 |oxlist[0|].c0max |
|00004390| 3d 20 4d 41 58 4a 53 41 | 4d 50 4c 45 20 3e 3e 20 |= MAXJSA|MPLE >> |
|000043a0| 59 5f 53 48 49 46 54 3b | 0a 58 20 20 62 6f 78 6c |Y_SHIFT;|.X boxl|
|000043b0| 69 73 74 5b 30 5d 2e 63 | 31 6d 69 6e 20 3d 20 30 |ist[0].c|1min = 0|
|000043c0| 3b 0a 58 20 20 62 6f 78 | 6c 69 73 74 5b 30 5d 2e |;.X box|list[0].|
|000043d0| 63 31 6d 61 78 20 3d 20 | 4d 41 58 4a 53 41 4d 50 |c1max = |MAXJSAMP|
|000043e0| 4c 45 20 3e 3e 20 43 5f | 53 48 49 46 54 3b 0a 58 |LE >> C_|SHIFT;.X|
|000043f0| 20 20 62 6f 78 6c 69 73 | 74 5b 30 5d 2e 63 32 6d | boxlis|t[0].c2m|
|00004400| 69 6e 20 3d 20 30 3b 0a | 58 20 20 62 6f 78 6c 69 |in = 0;.|X boxli|
|00004410| 73 74 5b 30 5d 2e 63 32 | 6d 61 78 20 3d 20 4d 41 |st[0].c2|max = MA|
|00004420| 58 4a 53 41 4d 50 4c 45 | 20 3e 3e 20 43 5f 53 48 |XJSAMPLE| >> C_SH|
|00004430| 49 46 54 3b 0a 58 20 20 | 2f 2a 20 53 68 72 69 6e |IFT;.X |/* Shrin|
|00004440| 6b 20 69 74 20 74 6f 20 | 61 63 74 75 61 6c 6c 79 |k it to |actually|
|00004450| 2d 75 73 65 64 20 76 6f | 6c 75 6d 65 20 61 6e 64 |-used vo|lume and|
|00004460| 20 73 65 74 20 69 74 73 | 20 73 74 61 74 69 73 74 | set its| statist|
|00004470| 69 63 73 20 2a 2f 0a 58 | 20 20 75 70 64 61 74 65 |ics */.X| update|
|00004480| 5f 62 6f 78 28 26 20 62 | 6f 78 6c 69 73 74 5b 30 |_box(& b|oxlist[0|
|00004490| 5d 29 3b 0a 58 20 20 2f | 2a 20 50 65 72 66 6f 72 |]);.X /|* Perfor|
|000044a0| 6d 20 6d 65 64 69 61 6e | 2d 63 75 74 20 74 6f 20 |m median|-cut to |
|000044b0| 70 72 6f 64 75 63 65 20 | 66 69 6e 61 6c 20 62 6f |produce |final bo|
|000044c0| 78 20 6c 69 73 74 20 2a | 2f 0a 58 20 20 6d 65 64 |x list *|/.X med|
|000044d0| 69 61 6e 5f 63 75 74 28 | 64 65 73 69 72 65 64 29 |ian_cut(|desired)|
|000044e0| 3b 0a 58 20 20 2f 2a 20 | 43 6f 6d 70 75 74 65 20 |;.X /* |Compute |
|000044f0| 74 68 65 20 72 65 70 72 | 65 73 65 6e 74 61 74 69 |the repr|esentati|
|00004500| 76 65 20 63 6f 6c 6f 72 | 20 66 6f 72 20 65 61 63 |ve color| for eac|
|00004510| 68 20 62 6f 78 2c 20 66 | 69 6c 6c 20 6d 79 5f 63 |h box, f|ill my_c|
|00004520| 6f 6c 6f 72 6d 61 70 5b | 5d 20 2a 2f 0a 58 20 20 |olormap[|] */.X |
|00004530| 66 6f 72 20 28 69 20 3d | 20 30 3b 20 69 20 3c 20 |for (i =| 0; i < |
|00004540| 6e 75 6d 62 6f 78 65 73 | 3b 20 69 2b 2b 29 0a 58 |numboxes|; i++).X|
|00004550| 20 20 20 20 63 6f 6d 70 | 75 74 65 5f 63 6f 6c 6f | comp|ute_colo|
|00004560| 72 28 26 20 62 6f 78 6c | 69 73 74 5b 69 5d 2c 20 |r(& boxl|ist[i], |
|00004570| 69 29 3b 0a 58 20 20 63 | 69 6e 66 6f 2d 3e 61 63 |i);.X c|info->ac|
|00004580| 74 75 61 6c 5f 6e 75 6d | 62 65 72 5f 6f 66 5f 63 |tual_num|ber_of_c|
|00004590| 6f 6c 6f 72 73 20 3d 20 | 6e 75 6d 62 6f 78 65 73 |olors = |numboxes|
|000045a0| 3b 0a 58 20 20 2f 2a 20 | 50 72 6f 64 75 63 65 20 |;.X /* |Produce |
|000045b0| 61 6e 20 6f 75 74 70 75 | 74 20 63 6f 6c 6f 72 6d |an outpu|t colorm|
|000045c0| 61 70 20 69 6e 20 74 68 | 65 20 64 65 73 69 72 65 |ap in th|e desire|
|000045d0| 64 20 6f 75 74 70 75 74 | 20 63 6f 6c 6f 72 73 70 |d output| colorsp|
|000045e0| 61 63 65 20 2a 2f 0a 58 | 20 20 72 65 6d 61 70 5f |ace */.X| remap_|
|000045f0| 63 6f 6c 6f 72 6d 61 70 | 28 63 69 6e 66 6f 29 3b |colormap|(cinfo);|
|00004600| 0a 58 20 20 54 52 41 43 | 45 4d 53 31 28 63 69 6e |.X TRAC|EMS1(cin|
|00004610| 66 6f 2d 3e 65 6d 65 74 | 68 6f 64 73 2c 20 31 2c |fo->emet|hods, 1,|
|00004620| 20 22 53 65 6c 65 63 74 | 65 64 20 25 64 20 63 6f | "Select|ed %d co|
|00004630| 6c 6f 72 73 20 66 6f 72 | 20 71 75 61 6e 74 69 7a |lors for| quantiz|
|00004640| 61 74 69 6f 6e 22 2c 0a | 58 09 20 20 20 6e 75 6d |ation",.|X. num|
|00004650| 62 6f 78 65 73 29 3b 0a | 58 20 20 2f 2a 20 44 6f |boxes);.|X /* Do|
|00004660| 6e 65 20 77 69 74 68 20 | 74 68 65 20 62 6f 78 20 |ne with |the box |
|00004670| 6c 69 73 74 20 2a 2f 0a | 58 20 20 28 2a 63 69 6e |list */.|X (*cin|
|00004680| 66 6f 2d 3e 65 6d 65 74 | 68 6f 64 73 2d 3e 66 72 |fo->emet|hods->fr|
|00004690| 65 65 5f 73 6d 61 6c 6c | 29 20 28 28 76 6f 69 64 |ee_small|) ((void|
|000046a0| 20 2a 29 20 62 6f 78 6c | 69 73 74 29 3b 0a 58 7d | *) boxl|ist);.X}|
|000046b0| 0a 58 0a 58 0a 58 2f 2a | 0a 58 20 2a 20 54 68 65 |.X.X.X/*|.X * The|
|000046c0| 73 65 20 72 6f 75 74 69 | 6e 65 73 20 61 72 65 20 |se routi|nes are |
|000046d0| 63 6f 6e 63 65 72 6e 65 | 64 20 77 69 74 68 20 74 |concerne|d with t|
|000046e0| 68 65 20 74 69 6d 65 2d | 63 72 69 74 69 63 61 6c |he time-|critical|
|000046f0| 20 74 61 73 6b 20 6f 66 | 20 6d 61 70 70 69 6e 67 | task of| mapping|
|00004700| 20 69 6e 70 75 74 0a 58 | 20 2a 20 63 6f 6c 6f 72 | input.X| * color|
|00004710| 73 20 74 6f 20 74 68 65 | 20 6e 65 61 72 65 73 74 |s to the| nearest|
|00004720| 20 63 6f 6c 6f 72 20 69 | 6e 20 74 68 65 20 73 65 | color i|n the se|
|00004730| 6c 65 63 74 65 64 20 63 | 6f 6c 6f 72 6d 61 70 2e |lected c|olormap.|
|00004740| 0a 58 20 2a 0a 58 20 2a | 20 57 65 20 72 65 2d 75 |.X *.X *| We re-u|
|00004750| 73 65 20 74 68 65 20 68 | 69 73 74 6f 67 72 61 6d |se the h|istogram|
|00004760| 20 73 70 61 63 65 20 61 | 73 20 61 6e 20 22 69 6e | space a|s an "in|
|00004770| 76 65 72 73 65 20 63 6f | 6c 6f 72 20 6d 61 70 22 |verse co|lor map"|
|00004780| 2c 20 65 73 73 65 6e 74 | 69 61 6c 6c 79 20 61 0a |, essent|ially a.|
|00004790| 58 20 2a 20 63 61 63 68 | 65 20 66 6f 72 20 74 68 |X * cach|e for th|
|000047a0| 65 20 72 65 73 75 6c 74 | 73 20 6f 66 20 6e 65 61 |e result|s of nea|
|000047b0| 72 65 73 74 2d 63 6f 6c | 6f 72 20 73 65 61 72 63 |rest-col|or searc|
|000047c0| 68 65 73 2e 20 20 41 6c | 6c 20 63 6f 6c 6f 72 73 |hes. Al|l colors|
|000047d0| 20 77 69 74 68 69 6e 20 | 61 0a 58 20 2a 20 68 69 | within |a.X * hi|
|000047e0| 73 74 6f 67 72 61 6d 20 | 63 65 6c 6c 20 77 69 6c |stogram |cell wil|
|000047f0| 6c 20 62 65 20 6d 61 70 | 70 65 64 20 74 6f 20 74 |l be map|ped to t|
|00004800| 68 65 20 73 61 6d 65 20 | 63 6f 6c 6f 72 6d 61 70 |he same |colormap|
|00004810| 20 65 6e 74 72 79 2c 20 | 6e 61 6d 65 6c 79 20 74 | entry, |namely t|
|00004820| 68 65 20 6f 6e 65 0a 58 | 20 2a 20 63 6c 6f 73 65 |he one.X| * close|
|00004830| 73 74 20 74 6f 20 74 68 | 65 20 63 65 6c 6c 27 73 |st to th|e cell's|
|00004840| 20 63 65 6e 74 65 72 2e | 20 20 54 68 69 73 20 6d | center.| This m|
|00004850| 61 79 20 6e 6f 74 20 62 | 65 20 71 75 69 74 65 20 |ay not b|e quite |
|00004860| 74 68 65 20 63 6c 6f 73 | 65 73 74 20 65 6e 74 72 |the clos|est entr|
|00004870| 79 20 74 6f 0a 58 20 2a | 20 74 68 65 20 61 63 74 |y to.X *| the act|
|00004880| 75 61 6c 20 69 6e 70 75 | 74 20 63 6f 6c 6f 72 2c |ual inpu|t color,|
|00004890| 20 62 75 74 20 69 74 27 | 73 20 61 6c 6d 6f 73 74 | but it'|s almost|
|000048a0| 20 61 73 20 67 6f 6f 64 | 2e 20 20 41 20 7a 65 72 | as good|. A zer|
|000048b0| 6f 20 69 6e 20 74 68 65 | 20 63 61 63 68 65 0a 58 |o in the| cache.X|
|000048c0| 20 2a 20 69 6e 64 69 63 | 61 74 65 73 20 77 65 20 | * indic|ates we |
|000048d0| 68 61 76 65 6e 27 74 20 | 66 6f 75 6e 64 20 74 68 |haven't |found th|
|000048e0| 65 20 6e 65 61 72 65 73 | 74 20 63 6f 6c 6f 72 20 |e neares|t color |
|000048f0| 66 6f 72 20 74 68 61 74 | 20 63 65 6c 6c 20 79 65 |for that| cell ye|
|00004900| 74 3b 20 74 68 65 20 61 | 72 72 61 79 0a 58 20 2a |t; the a|rray.X *|
|00004910| 20 69 73 20 63 6c 65 61 | 72 65 64 20 74 6f 20 7a | is clea|red to z|
|00004920| 65 72 6f 65 73 20 62 65 | 66 6f 72 65 20 73 74 61 |eroes be|fore sta|
|00004930| 72 74 69 6e 67 20 74 68 | 65 20 6d 61 70 70 69 6e |rting th|e mappin|
|00004940| 67 20 70 61 73 73 2e 20 | 20 57 68 65 6e 20 77 65 |g pass. | When we|
|00004950| 20 66 69 6e 64 20 74 68 | 65 0a 58 20 2a 20 6e 65 | find th|e.X * ne|
|00004960| 61 72 65 73 74 20 63 6f | 6c 6f 72 20 66 6f 72 20 |arest co|lor for |
|00004970| 61 20 63 65 6c 6c 2c 20 | 69 74 73 20 63 6f 6c 6f |a cell, |its colo|
|00004980| 72 6d 61 70 20 69 6e 64 | 65 78 20 70 6c 75 73 20 |rmap ind|ex plus |
|00004990| 6f 6e 65 20 69 73 20 72 | 65 63 6f 72 64 65 64 20 |one is r|ecorded |
|000049a0| 69 6e 20 74 68 65 0a 58 | 20 2a 20 63 61 63 68 65 |in the.X| * cache|
|000049b0| 20 66 6f 72 20 66 75 74 | 75 72 65 20 75 73 65 2e | for fut|ure use.|
|000049c0| 20 20 54 68 65 20 70 61 | 73 73 32 20 73 63 61 6e | The pa|ss2 scan|
|000049d0| 6e 69 6e 67 20 72 6f 75 | 74 69 6e 65 73 20 63 61 |ning rou|tines ca|
|000049e0| 6c 6c 20 66 69 6c 6c 5f | 69 6e 76 65 72 73 65 5f |ll fill_|inverse_|
|000049f0| 63 6d 61 70 0a 58 20 2a | 20 77 68 65 6e 20 74 68 |cmap.X *| when th|
|00004a00| 65 79 20 6e 65 65 64 20 | 74 6f 20 75 73 65 20 61 |ey need |to use a|
|00004a10| 6e 20 75 6e 66 69 6c 6c | 65 64 20 65 6e 74 72 79 |n unfill|ed entry|
|00004a20| 20 69 6e 20 74 68 65 20 | 63 61 63 68 65 2e 0a 58 | in the |cache..X|
|00004a30| 20 2a 0a 58 20 2a 20 4f | 75 72 20 6d 65 74 68 6f | *.X * O|ur metho|
|00004a40| 64 20 6f 66 20 65 66 66 | 69 63 69 65 6e 74 6c 79 |d of eff|iciently|
|00004a50| 20 66 69 6e 64 69 6e 67 | 20 6e 65 61 72 65 73 74 | finding| nearest|
|00004a60| 20 63 6f 6c 6f 72 73 20 | 69 73 20 62 61 73 65 64 | colors |is based|
|00004a70| 20 6f 6e 20 74 68 65 20 | 22 6c 6f 63 61 6c 6c 79 | on the |"locally|
|00004a80| 0a 58 20 2a 20 73 6f 72 | 74 65 64 20 73 65 61 72 |.X * sor|ted sear|
|00004a90| 63 68 22 20 69 64 65 61 | 20 64 65 73 63 72 69 62 |ch" idea| describ|
|00004aa0| 65 64 20 62 79 20 48 65 | 63 6b 62 65 72 74 20 61 |ed by He|ckbert a|
|00004ab0| 6e 64 20 6f 6e 20 74 68 | 65 20 69 6e 63 72 65 6d |nd on th|e increm|
|00004ac0| 65 6e 74 61 6c 20 64 69 | 73 74 61 6e 63 65 0a 58 |ental di|stance.X|
|00004ad0| 20 2a 20 63 61 6c 63 75 | 6c 61 74 69 6f 6e 20 64 | * calcu|lation d|
|00004ae0| 65 73 63 72 69 62 65 64 | 20 62 79 20 53 70 65 6e |escribed| by Spen|
|00004af0| 63 65 72 20 57 2e 20 54 | 68 6f 6d 61 73 20 69 6e |cer W. T|homas in|
|00004b00| 20 63 68 61 70 74 65 72 | 20 49 49 49 2e 31 20 6f | chapter| III.1 o|
|00004b10| 66 20 47 72 61 70 68 69 | 63 73 0a 58 20 2a 20 47 |f Graphi|cs.X * G|
|00004b20| 65 6d 73 20 49 49 20 28 | 4a 61 6d 65 73 20 41 72 |ems II (|James Ar|
|00004b30| 76 6f 2c 20 65 64 2e 20 | 20 41 63 61 64 65 6d 69 |vo, ed. | Academi|
|00004b40| 63 20 50 72 65 73 73 2c | 20 31 39 39 31 29 2e 20 |c Press,| 1991). |
|00004b50| 20 54 68 6f 6d 61 73 20 | 70 6f 69 6e 74 73 20 6f | Thomas |points o|
|00004b60| 75 74 20 74 68 61 74 0a | 58 20 2a 20 74 68 65 20 |ut that.|X * the |
|00004b70| 64 69 73 74 61 6e 63 65 | 73 20 66 72 6f 6d 20 61 |distance|s from a|
|00004b80| 20 67 69 76 65 6e 20 63 | 6f 6c 6f 72 6d 61 70 20 | given c|olormap |
|00004b90| 65 6e 74 72 79 20 74 6f | 20 65 61 63 68 20 63 65 |entry to| each ce|
|00004ba0| 6c 6c 20 6f 66 20 74 68 | 65 20 68 69 73 74 6f 67 |ll of th|e histog|
|00004bb0| 72 61 6d 20 63 61 6e 0a | 58 20 2a 20 62 65 20 63 |ram can.|X * be c|
|00004bc0| 6f 6d 70 75 74 65 64 20 | 71 75 69 63 6b 6c 79 20 |omputed |quickly |
|00004bd0| 75 73 69 6e 67 20 61 6e | 20 69 6e 63 72 65 6d 65 |using an| increme|
|00004be0| 6e 74 61 6c 20 6d 65 74 | 68 6f 64 3a 20 74 68 65 |ntal met|hod: the|
|00004bf0| 20 64 69 66 66 65 72 65 | 6e 63 65 73 20 62 65 74 | differe|nces bet|
|00004c00| 77 65 65 6e 0a 58 20 2a | 20 64 69 73 74 61 6e 63 |ween.X *| distanc|
|00004c10| 65 73 20 74 6f 20 61 64 | 6a 61 63 65 6e 74 20 63 |es to ad|jacent c|
|00004c20| 65 6c 6c 73 20 74 68 65 | 6d 73 65 6c 76 65 73 20 |ells the|mselves |
|00004c30| 64 69 66 66 65 72 20 62 | 79 20 61 20 63 6f 6e 73 |differ b|y a cons|
|00004c40| 74 61 6e 74 2e 20 20 54 | 68 69 73 20 61 6c 6c 6f |tant. T|his allo|
|00004c50| 77 73 20 61 0a 58 20 2a | 20 66 61 69 72 6c 79 20 |ws a.X *| fairly |
|00004c60| 66 61 73 74 20 69 6d 70 | 6c 65 6d 65 6e 74 61 74 |fast imp|lementat|
|00004c70| 69 6f 6e 20 6f 66 20 74 | 68 65 20 22 62 72 75 74 |ion of t|he "brut|
|00004c80| 65 20 66 6f 72 63 65 22 | 20 61 70 70 72 6f 61 63 |e force"| approac|
|00004c90| 68 20 6f 66 20 63 6f 6d | 70 75 74 69 6e 67 20 74 |h of com|puting t|
|00004ca0| 68 65 0a 58 20 2a 20 64 | 69 73 74 61 6e 63 65 20 |he.X * d|istance |
|00004cb0| 66 72 6f 6d 20 65 76 65 | 72 79 20 63 6f 6c 6f 72 |from eve|ry color|
|00004cc0| 6d 61 70 20 65 6e 74 72 | 79 20 74 6f 20 65 76 65 |map entr|y to eve|
|00004cd0| 72 79 20 68 69 73 74 6f | 67 72 61 6d 20 63 65 6c |ry histo|gram cel|
|00004ce0| 6c 2e 20 20 55 6e 66 6f | 72 74 75 6e 61 74 65 6c |l. Unfo|rtunatel|
|00004cf0| 79 2c 0a 58 20 2a 20 69 | 74 20 6e 65 65 64 73 20 |y,.X * i|t needs |
|00004d00| 61 20 77 6f 72 6b 20 61 | 72 72 61 79 20 74 6f 20 |a work a|rray to |
|00004d10| 68 6f 6c 64 20 74 68 65 | 20 62 65 73 74 2d 64 69 |hold the| best-di|
|00004d20| 73 74 61 6e 63 65 2d 73 | 6f 2d 66 61 72 20 66 6f |stance-s|o-far fo|
|00004d30| 72 20 65 61 63 68 20 68 | 69 73 74 6f 67 72 61 6d |r each h|istogram|
|00004d40| 0a 58 20 2a 20 63 65 6c | 6c 20 28 62 65 63 61 75 |.X * cel|l (becau|
|00004d50| 73 65 20 74 68 65 20 69 | 6e 6e 65 72 20 6c 6f 6f |se the i|nner loo|
|00004d60| 70 20 68 61 73 20 74 6f | 20 62 65 20 6f 76 65 72 |p has to| be over|
|00004d70| 20 63 65 6c 6c 73 2c 20 | 6e 6f 74 20 63 6f 6c 6f | cells, |not colo|
|00004d80| 72 6d 61 70 20 65 6e 74 | 72 69 65 73 29 2e 0a 58 |rmap ent|ries)..X|
|00004d90| 20 2a 20 54 68 65 20 77 | 6f 72 6b 20 61 72 72 61 | * The w|ork arra|
|00004da0| 79 20 65 6c 65 6d 65 6e | 74 73 20 68 61 76 65 20 |y elemen|ts have |
|00004db0| 74 6f 20 62 65 20 49 4e | 54 33 32 73 2c 20 73 6f |to be IN|T32s, so|
|00004dc0| 20 74 68 65 20 77 6f 72 | 6b 20 61 72 72 61 79 20 | the wor|k array |
|00004dd0| 77 6f 75 6c 64 20 6e 65 | 65 64 0a 58 20 2a 20 32 |would ne|ed.X * 2|
|00004de0| 35 36 4b 62 20 61 74 20 | 6f 75 72 20 72 65 63 6f |56Kb at |our reco|
|00004df0| 6d 6d 65 6e 64 65 64 20 | 70 72 65 63 69 73 69 6f |mmended |precisio|
|00004e00| 6e 2e 20 20 54 68 69 73 | 20 69 73 20 6e 6f 74 20 |n. This| is not |
|00004e10| 66 65 61 73 69 62 6c 65 | 20 69 6e 20 44 4f 53 20 |feasible| in DOS |
|00004e20| 6d 61 63 68 69 6e 65 73 | 2e 0a 58 20 2a 20 41 6e |machines|..X * An|
|00004e30| 6f 74 68 65 72 20 64 69 | 73 61 64 76 61 6e 74 61 |other di|sadvanta|
|00004e40| 67 65 20 6f 66 20 74 68 | 65 20 62 72 75 74 65 20 |ge of th|e brute |
|00004e50| 66 6f 72 63 65 20 61 70 | 70 72 6f 61 63 68 20 69 |force ap|proach i|
|00004e60| 73 20 74 68 61 74 20 69 | 74 20 63 6f 6d 70 75 74 |s that i|t comput|
|00004e70| 65 73 0a 58 20 2a 20 64 | 69 73 74 61 6e 63 65 73 |es.X * d|istances|
|00004e80| 20 74 6f 20 65 76 65 72 | 79 20 63 65 6c 6c 20 6f | to ever|y cell o|
|00004e90| 66 20 74 68 65 20 63 75 | 62 69 63 61 6c 20 68 69 |f the cu|bical hi|
|00004ea0| 73 74 6f 67 72 61 6d 2e | 20 20 57 68 65 6e 20 77 |stogram.| When w|
|00004eb0| 6f 72 6b 69 6e 67 20 77 | 69 74 68 20 59 43 62 43 |orking w|ith YCbC|
|00004ec0| 72 0a 58 20 2a 20 69 6e | 70 75 74 2c 20 6f 6e 6c |r.X * in|put, onl|
|00004ed0| 79 20 61 62 6f 75 74 20 | 61 20 71 75 61 72 74 65 |y about |a quarte|
|00004ee0| 72 20 6f 66 20 74 68 65 | 20 63 75 62 65 20 72 65 |r of the| cube re|
|00004ef0| 70 72 65 73 65 6e 74 73 | 20 72 65 61 6c 69 7a 61 |presents| realiza|
|00004f00| 62 6c 65 20 63 6f 6c 6f | 72 73 2c 20 73 6f 0a 58 |ble colo|rs, so.X|
|00004f10| 20 2a 20 6d 61 6e 79 20 | 6f 66 20 74 68 65 20 63 | * many |of the c|
|00004f20| 65 6c 6c 73 20 77 69 6c | 6c 20 6e 65 76 65 72 20 |ells wil|l never |
|00004f30| 62 65 20 75 73 65 64 20 | 61 6e 64 20 66 69 6c 6c |be used |and fill|
|00004f40| 69 6e 67 20 74 68 65 6d | 20 69 73 20 77 61 73 74 |ing them| is wast|
|00004f50| 65 64 20 65 66 66 6f 72 | 74 2e 0a 58 20 2a 0a 58 |ed effor|t..X *.X|
|00004f60| 20 2a 20 54 6f 20 67 65 | 74 20 61 72 6f 75 6e 64 | * To ge|t around|
|00004f70| 20 74 68 65 73 65 20 70 | 72 6f 62 6c 65 6d 73 2c | these p|roblems,|
|00004f80| 20 77 65 20 61 70 70 6c | 79 20 54 68 6f 6d 61 73 | we appl|y Thomas|
|00004f90| 27 20 6d 65 74 68 6f 64 | 20 74 6f 20 63 6f 6d 70 |' method| to comp|
|00004fa0| 75 74 65 20 74 68 65 0a | 58 20 2a 20 6e 65 61 72 |ute the.|X * near|
|00004fb0| 65 73 74 20 63 6f 6c 6f | 72 73 20 66 6f 72 20 6f |est colo|rs for o|
|00004fc0| 6e 6c 79 20 74 68 65 20 | 63 65 6c 6c 73 20 77 69 |nly the |cells wi|
|00004fd0| 74 68 69 6e 20 61 20 73 | 6d 61 6c 6c 20 73 75 62 |thin a s|mall sub|
|00004fe0| 62 6f 78 20 6f 66 20 74 | 68 65 20 68 69 73 74 6f |box of t|he histo|
|00004ff0| 67 72 61 6d 2e 0a 58 20 | 2a 20 54 68 65 20 77 6f |gram..X |* The wo|
|00005000| 72 6b 20 61 72 72 61 79 | 20 6e 65 65 64 20 62 65 |rk array| need be|
|00005010| 20 6f 6e 6c 79 20 61 73 | 20 62 69 67 20 61 73 20 | only as| big as |
|00005020| 74 68 65 20 73 75 62 62 | 6f 78 2c 20 73 6f 20 74 |the subb|ox, so t|
|00005030| 68 65 20 6d 65 6d 6f 72 | 79 20 75 73 61 67 65 0a |he memor|y usage.|
|00005040| 58 20 2a 20 70 72 6f 62 | 6c 65 6d 20 69 73 20 73 |X * prob|lem is s|
|00005050| 6f 6c 76 65 64 2e 20 20 | 41 20 73 75 62 62 6f 78 |olved. |A subbox|
|00005060| 20 69 73 20 70 72 6f 63 | 65 73 73 65 64 20 6f 6e | is proc|essed on|
|00005070| 6c 79 20 77 68 65 6e 20 | 73 6f 6d 65 20 63 65 6c |ly when |some cel|
|00005080| 6c 20 69 6e 20 69 74 20 | 69 73 0a 58 20 2a 20 72 |l in it |is.X * r|
|00005090| 65 66 65 72 65 6e 63 65 | 64 20 62 79 20 74 68 65 |eference|d by the|
|000050a0| 20 70 61 73 73 32 20 72 | 6f 75 74 69 6e 65 73 2c | pass2 r|outines,|
|000050b0| 20 73 6f 20 77 65 20 77 | 69 6c 6c 20 6e 65 76 65 | so we w|ill neve|
|000050c0| 72 20 62 6f 74 68 65 72 | 20 77 69 74 68 20 63 65 |r bother| with ce|
|000050d0| 6c 6c 73 20 66 61 72 0a | 58 20 2a 20 6f 75 74 73 |lls far.|X * outs|
|000050e0| 69 64 65 20 74 68 65 20 | 72 65 61 6c 69 7a 61 62 |ide the |realizab|
|000050f0| 6c 65 20 63 6f 6c 6f 72 | 20 76 6f 6c 75 6d 65 2e |le color| volume.|
|00005100| 20 20 41 6e 20 61 64 64 | 69 74 69 6f 6e 61 6c 20 | An add|itional |
|00005110| 61 64 76 61 6e 74 61 67 | 65 20 6f 66 20 74 68 69 |advantag|e of thi|
|00005120| 73 0a 58 20 2a 20 61 70 | 70 72 6f 61 63 68 20 69 |s.X * ap|proach i|
|00005130| 73 20 74 68 61 74 20 77 | 65 20 63 61 6e 20 61 70 |s that w|e can ap|
|00005140| 70 6c 79 20 48 65 63 6b | 62 65 72 74 27 73 20 6c |ply Heck|bert's l|
|00005150| 6f 63 61 6c 69 74 79 20 | 63 72 69 74 65 72 69 6f |ocality |criterio|
|00005160| 6e 20 74 6f 20 71 75 69 | 63 6b 6c 79 0a 58 20 2a |n to qui|ckly.X *|
|00005170| 20 65 6c 69 6d 69 6e 61 | 74 65 20 63 6f 6c 6f 72 | elimina|te color|
|00005180| 6d 61 70 20 65 6e 74 72 | 69 65 73 20 74 68 61 74 |map entr|ies that|
|00005190| 20 61 72 65 20 66 61 72 | 20 61 77 61 79 20 66 72 | are far| away fr|
|000051a0| 6f 6d 20 74 68 65 20 73 | 75 62 62 6f 78 3b 20 74 |om the s|ubbox; t|
|000051b0| 79 70 69 63 61 6c 6c 79 | 0a 58 20 2a 20 74 68 72 |ypically|.X * thr|
|000051c0| 65 65 2d 66 6f 75 72 74 | 68 73 20 6f 66 20 74 68 |ee-fourt|hs of th|
|000051d0| 65 20 63 6f 6c 6f 72 6d | 61 70 20 65 6e 74 72 69 |e colorm|ap entri|
|000051e0| 65 73 20 61 72 65 20 72 | 65 6a 65 63 74 65 64 20 |es are r|ejected |
|000051f0| 62 79 20 48 65 63 6b 62 | 65 72 74 27 73 20 63 72 |by Heckb|ert's cr|
|00005200| 69 74 65 72 69 6f 6e 2c | 0a 58 20 2a 20 61 6e 64 |iterion,|.X * and|
|00005210| 20 77 65 20 6e 65 65 64 | 20 6e 6f 74 20 63 6f 6d | we need| not com|
|00005220| 70 75 74 65 20 74 68 65 | 69 72 20 64 69 73 74 61 |pute the|ir dista|
|00005230| 6e 63 65 73 20 74 6f 20 | 69 6e 64 69 76 69 64 75 |nces to |individu|
|00005240| 61 6c 20 63 65 6c 6c 73 | 20 69 6e 20 74 68 65 20 |al cells| in the |
|00005250| 73 75 62 62 6f 78 2e 0a | 58 20 2a 20 54 68 65 20 |subbox..|X * The |
|00005260| 73 70 65 65 64 20 6f 66 | 20 74 68 69 73 20 61 70 |speed of| this ap|
|00005270| 70 72 6f 61 63 68 20 69 | 73 20 68 65 61 76 69 6c |proach i|s heavil|
|00005280| 79 20 69 6e 66 6c 75 65 | 6e 63 65 64 20 62 79 20 |y influe|nced by |
|00005290| 74 68 65 20 73 75 62 62 | 6f 78 20 73 69 7a 65 3a |the subb|ox size:|
|000052a0| 20 74 6f 6f 0a 58 20 2a | 20 73 6d 61 6c 6c 20 6d | too.X *| small m|
|000052b0| 65 61 6e 73 20 74 6f 6f | 20 6d 75 63 68 20 6f 76 |eans too| much ov|
|000052c0| 65 72 68 65 61 64 2c 20 | 74 6f 6f 20 62 69 67 20 |erhead, |too big |
|000052d0| 6c 6f 73 65 73 20 62 65 | 63 61 75 73 65 20 48 65 |loses be|cause He|
|000052e0| 63 6b 62 65 72 74 27 73 | 20 63 72 69 74 65 72 69 |ckbert's| criteri|
|000052f0| 6f 6e 0a 58 20 2a 20 63 | 61 6e 27 74 20 65 6c 69 |on.X * c|an't eli|
|00005300| 6d 69 6e 61 74 65 20 61 | 73 20 6d 61 6e 79 20 63 |minate a|s many c|
|00005310| 6f 6c 6f 72 6d 61 70 20 | 65 6e 74 72 69 65 73 2e |olormap |entries.|
|00005320| 20 20 45 6d 70 69 72 69 | 63 61 6c 6c 79 20 74 68 | Empiri|cally th|
|00005330| 65 20 62 65 73 74 20 73 | 75 62 62 6f 78 0a 58 20 |e best s|ubbox.X |
|00005340| 2a 20 73 69 7a 65 20 73 | 65 65 6d 73 20 74 6f 20 |* size s|eems to |
|00005350| 62 65 20 61 62 6f 75 74 | 20 31 2f 35 31 32 74 68 |be about| 1/512th|
|00005360| 20 6f 66 20 74 68 65 20 | 68 69 73 74 6f 67 72 61 | of the |histogra|
|00005370| 6d 20 28 31 2f 38 74 68 | 20 69 6e 20 65 61 63 68 |m (1/8th| in each|
|00005380| 20 64 69 72 65 63 74 69 | 6f 6e 29 2e 0a 58 20 2a | directi|on)..X *|
|00005390| 0a 58 20 2a 20 54 68 6f | 6d 61 73 27 20 61 72 74 |.X * Tho|mas' art|
|000053a0| 69 63 6c 65 20 61 6c 73 | 6f 20 64 65 73 63 72 69 |icle als|o descri|
|000053b0| 62 65 73 20 61 20 72 65 | 66 69 6e 65 64 20 6d 65 |bes a re|fined me|
|000053c0| 74 68 6f 64 20 77 68 69 | 63 68 20 69 73 20 61 73 |thod whi|ch is as|
|000053d0| 79 6d 70 74 6f 74 69 63 | 61 6c 6c 79 0a 58 20 2a |ymptotic|ally.X *|
|000053e0| 20 66 61 73 74 65 72 20 | 74 68 61 6e 20 74 68 65 | faster |than the|
|000053f0| 20 62 72 75 74 65 2d 66 | 6f 72 63 65 20 6d 65 74 | brute-f|orce met|
|00005400| 68 6f 64 2c 20 62 75 74 | 20 69 74 20 69 73 20 61 |hod, but| it is a|
|00005410| 6c 73 6f 20 66 61 72 20 | 6d 6f 72 65 20 63 6f 6d |lso far |more com|
|00005420| 70 6c 65 78 20 61 6e 64 | 0a 58 20 2a 20 63 61 6e |plex and|.X * can|
|00005430| 6e 6f 74 20 65 66 66 69 | 63 69 65 6e 74 6c 79 20 |not effi|ciently |
|00005440| 62 65 20 61 70 70 6c 69 | 65 64 20 74 6f 20 73 6d |be appli|ed to sm|
|00005450| 61 6c 6c 20 73 75 62 62 | 6f 78 65 73 2e 20 20 49 |all subb|oxes. I|
|00005460| 74 20 69 73 20 74 68 65 | 72 65 66 6f 72 65 20 6e |t is the|refore n|
|00005470| 6f 74 0a 58 20 2a 20 75 | 73 65 66 75 6c 20 66 6f |ot.X * u|seful fo|
|00005480| 72 20 70 72 6f 67 72 61 | 6d 73 20 69 6e 74 65 6e |r progra|ms inten|
|00005490| 64 65 64 20 74 6f 20 62 | 65 20 70 6f 72 74 61 62 |ded to b|e portab|
|000054a0| 6c 65 20 74 6f 20 44 4f | 53 20 6d 61 63 68 69 6e |le to DO|S machin|
|000054b0| 65 73 2e 20 20 4f 6e 20 | 6d 61 63 68 69 6e 65 73 |es. On |machines|
|000054c0| 0a 58 20 2a 20 77 69 74 | 68 20 70 6c 65 6e 74 79 |.X * wit|h plenty|
|000054d0| 20 6f 66 20 6d 65 6d 6f | 72 79 2c 20 66 69 6c 6c | of memo|ry, fill|
|000054e0| 69 6e 67 20 74 68 65 20 | 77 68 6f 6c 65 20 68 69 |ing the |whole hi|
|000054f0| 73 74 6f 67 72 61 6d 20 | 69 6e 20 6f 6e 65 20 73 |stogram |in one s|
|00005500| 68 6f 74 20 77 69 74 68 | 20 54 68 6f 6d 61 73 27 |hot with| Thomas'|
|00005510| 0a 58 20 2a 20 72 65 66 | 69 6e 65 64 20 6d 65 74 |.X * ref|ined met|
|00005520| 68 6f 64 20 6d 69 67 68 | 74 20 62 65 20 66 61 73 |hod migh|t be fas|
|00005530| 74 65 72 20 74 68 61 6e | 20 74 68 65 20 70 72 65 |ter than| the pre|
|00005540| 73 65 6e 74 20 63 6f 64 | 65 20 2d 2d 2d 20 62 75 |sent cod|e --- bu|
|00005550| 74 20 74 68 65 6e 20 61 | 67 61 69 6e 2c 0a 58 20 |t then a|gain,.X |
|00005560| 2a 20 69 74 20 6d 69 67 | 68 74 20 6e 6f 74 20 62 |* it mig|ht not b|
|00005570| 65 20 61 6e 79 20 66 61 | 73 74 65 72 2c 20 61 6e |e any fa|ster, an|
|00005580| 64 20 69 74 27 73 20 63 | 65 72 74 61 69 6e 6c 79 |d it's c|ertainly|
|00005590| 20 6d 6f 72 65 20 63 6f | 6d 70 6c 69 63 61 74 65 | more co|mplicate|
|000055a0| 64 2e 0a 58 20 2a 2f 0a | 58 0a 58 0a 58 23 69 66 |d..X */.|X.X.X#if|
|000055b0| 6e 64 65 66 20 42 4f 58 | 5f 59 5f 4c 4f 47 09 09 |ndef BOX|_Y_LOG..|
|000055c0| 2f 2a 20 73 6f 20 79 6f | 75 20 63 61 6e 20 6f 76 |/* so yo|u can ov|
|000055d0| 65 72 72 69 64 65 20 66 | 72 6f 6d 20 4d 61 6b 65 |erride f|rom Make|
|000055e0| 66 69 6c 65 20 2a 2f 0a | 58 23 64 65 66 69 6e 65 |file */.|X#define|
|000055f0| 20 42 4f 58 5f 59 5f 4c | 4f 47 20 20 28 48 49 53 | BOX_Y_L|OG (HIS|
|00005600| 54 5f 59 5f 42 49 54 53 | 2d 33 29 20 2f 2a 20 6c |T_Y_BITS|-3) /* l|
|00005610| 6f 67 32 28 68 69 73 74 | 20 63 65 6c 6c 73 20 69 |og2(hist| cells i|
|00005620| 6e 20 75 70 64 61 74 65 | 20 62 6f 78 2c 20 59 20 |n update| box, Y |
|00005630| 61 78 69 73 29 20 2a 2f | 0a 58 23 65 6e 64 69 66 |axis) */|.X#endif|
|00005640| 0a 58 23 69 66 6e 64 65 | 66 20 42 4f 58 5f 43 5f |.X#ifnde|f BOX_C_|
|00005650| 4c 4f 47 09 09 2f 2a 20 | 73 6f 20 79 6f 75 20 63 |LOG../* |so you c|
|00005660| 61 6e 20 6f 76 65 72 72 | 69 64 65 20 66 72 6f 6d |an overr|ide from|
|00005670| 20 4d 61 6b 65 66 69 6c | 65 20 2a 2f 0a 58 23 64 | Makefil|e */.X#d|
|00005680| 65 66 69 6e 65 20 42 4f | 58 5f 43 5f 4c 4f 47 20 |efine BO|X_C_LOG |
|00005690| 20 28 48 49 53 54 5f 43 | 5f 42 49 54 53 2d 33 29 | (HIST_C|_BITS-3)|
|000056a0| 20 2f 2a 20 6c 6f 67 32 | 28 68 69 73 74 20 63 65 | /* log2|(hist ce|
|000056b0| 6c 6c 73 20 69 6e 20 75 | 70 64 61 74 65 20 62 6f |lls in u|pdate bo|
|000056c0| 78 2c 20 43 20 61 78 65 | 73 29 20 2a 2f 0a 58 23 |x, C axe|s) */.X#|
|000056d0| 65 6e 64 69 66 0a 58 0a | 58 23 64 65 66 69 6e 65 |endif.X.|X#define|
|000056e0| 20 42 4f 58 5f 59 5f 45 | 4c 45 4d 53 20 20 28 31 | BOX_Y_E|LEMS (1|
|000056f0| 3c 3c 42 4f 58 5f 59 5f | 4c 4f 47 29 20 2f 2a 20 |<<BOX_Y_|LOG) /* |
|00005700| 23 20 6f 66 20 68 69 73 | 74 20 63 65 6c 6c 73 20 |# of his|t cells |
|00005710| 69 6e 20 75 70 64 61 74 | 65 20 62 6f 78 20 2a 2f |in updat|e box */|
|00005720| 0a 58 23 64 65 66 69 6e | 65 20 42 4f 58 5f 43 5f |.X#defin|e BOX_C_|
|00005730| 45 4c 45 4d 53 20 20 28 | 31 3c 3c 42 4f 58 5f 43 |ELEMS (|1<<BOX_C|
|00005740| 5f 4c 4f 47 29 0a 58 0a | 58 23 64 65 66 69 6e 65 |_LOG).X.|X#define|
|00005750| 20 42 4f 58 5f 59 5f 53 | 48 49 46 54 20 20 28 59 | BOX_Y_S|HIFT (Y|
|00005760| 5f 53 48 49 46 54 20 2b | 20 42 4f 58 5f 59 5f 4c |_SHIFT +| BOX_Y_L|
|00005770| 4f 47 29 0a 58 23 64 65 | 66 69 6e 65 20 42 4f 58 |OG).X#de|fine BOX|
|00005780| 5f 43 5f 53 48 49 46 54 | 20 20 28 43 5f 53 48 49 |_C_SHIFT| (C_SHI|
|00005790| 46 54 20 2b 20 42 4f 58 | 5f 43 5f 4c 4f 47 29 0a |FT + BOX|_C_LOG).|
|000057a0| 58 0a 58 0a 58 2f 2a 0a | 58 20 2a 20 54 68 65 20 |X.X.X/*.|X * The |
|000057b0| 6e 65 78 74 20 74 68 72 | 65 65 20 72 6f 75 74 69 |next thr|ee routi|
|000057c0| 6e 65 73 20 69 6d 70 6c | 65 6d 65 6e 74 20 69 6e |nes impl|ement in|
|000057d0| 76 65 72 73 65 20 63 6f | 6c 6f 72 6d 61 70 20 66 |verse co|lormap f|
|000057e0| 69 6c 6c 69 6e 67 2e 20 | 20 54 68 65 79 20 63 6f |illing. | They co|
|000057f0| 75 6c 64 0a 58 20 2a 20 | 61 6c 6c 20 62 65 20 66 |uld.X * |all be f|
|00005800| 6f 6c 64 65 64 20 69 6e | 74 6f 20 6f 6e 65 20 62 |olded in|to one b|
|00005810| 69 67 20 72 6f 75 74 69 | 6e 65 2c 20 62 75 74 20 |ig routi|ne, but |
|00005820| 73 70 6c 69 74 74 69 6e | 67 20 74 68 65 6d 20 75 |splittin|g them u|
|00005830| 70 20 74 68 69 73 20 77 | 61 79 20 73 61 76 65 73 |p this w|ay saves|
|00005840| 0a 58 20 2a 20 73 6f 6d | 65 20 73 74 61 63 6b 20 |.X * som|e stack |
|00005850| 73 70 61 63 65 20 28 74 | 68 65 20 6d 69 6e 64 69 |space (t|he mindi|
|00005860| 73 74 5b 5d 20 61 6e 64 | 20 62 65 73 74 64 69 73 |st[] and| bestdis|
|00005870| 74 5b 5d 20 61 72 72 61 | 79 73 20 6e 65 65 64 20 |t[] arra|ys need |
|00005880| 6e 6f 74 20 63 6f 65 78 | 69 73 74 29 0a 58 20 2a |not coex|ist).X *|
|00005890| 20 61 6e 64 20 6d 61 79 | 20 61 6c 6c 6f 77 20 73 | and may| allow s|
|000058a0| 6f 6d 65 20 63 6f 6d 70 | 69 6c 65 72 73 20 74 6f |ome comp|ilers to|
|000058b0| 20 70 72 6f 64 75 63 65 | 20 62 65 74 74 65 72 20 | produce| better |
|000058c0| 63 6f 64 65 20 62 79 20 | 72 65 67 69 73 74 65 72 |code by |register|
|000058d0| 69 7a 69 6e 67 20 6d 6f | 72 65 0a 58 20 2a 20 69 |izing mo|re.X * i|
|000058e0| 6e 6e 65 72 2d 6c 6f 6f | 70 20 76 61 72 69 61 62 |nner-loo|p variab|
|000058f0| 6c 65 73 2e 0a 58 20 2a | 2f 0a 58 0a 58 4c 4f 43 |les..X *|/.X.XLOC|
|00005900| 41 4c 20 69 6e 74 0a 58 | 66 69 6e 64 5f 6e 65 61 |AL int.X|find_nea|
|00005910| 72 62 79 5f 63 6f 6c 6f | 72 73 20 28 64 65 63 6f |rby_colo|rs (deco|
|00005920| 6d 70 72 65 73 73 5f 69 | 6e 66 6f 5f 70 74 72 20 |mpress_i|nfo_ptr |
|00005930| 63 69 6e 66 6f 2c 20 69 | 6e 74 20 6d 69 6e 63 30 |cinfo, i|nt minc0|
|00005940| 2c 20 69 6e 74 20 6d 69 | 6e 63 31 2c 20 69 6e 74 |, int mi|nc1, int|
|00005950| 20 6d 69 6e 63 32 2c 0a | 58 09 09 20 20 20 20 4a | minc2,.|X.. J|
|00005960| 53 41 4d 50 4c 45 20 63 | 6f 6c 6f 72 6c 69 73 74 |SAMPLE c|olorlist|
|00005970| 5b 5d 29 0a 58 2f 2a 20 | 4c 6f 63 61 74 65 20 74 |[]).X/* |Locate t|
|00005980| 68 65 20 63 6f 6c 6f 72 | 6d 61 70 20 65 6e 74 72 |he color|map entr|
|00005990| 69 65 73 20 63 6c 6f 73 | 65 20 65 6e 6f 75 67 68 |ies clos|e enough|
|000059a0| 20 74 6f 20 61 6e 20 75 | 70 64 61 74 65 20 62 6f | to an u|pdate bo|
|000059b0| 78 20 74 6f 20 62 65 20 | 63 61 6e 64 69 64 61 74 |x to be |candidat|
|000059c0| 65 73 0a 58 20 2a 20 66 | 6f 72 20 74 68 65 20 6e |es.X * f|or the n|
|000059d0| 65 61 72 65 73 74 20 65 | 6e 74 72 79 20 74 6f 20 |earest e|ntry to |
|000059e0| 73 6f 6d 65 20 63 65 6c | 6c 28 73 29 20 69 6e 20 |some cel|l(s) in |
|000059f0| 74 68 65 20 75 70 64 61 | 74 65 20 62 6f 78 2e 20 |the upda|te box. |
|00005a00| 20 54 68 65 20 75 70 64 | 61 74 65 20 62 6f 78 0a | The upd|ate box.|
|00005a10| 58 20 2a 20 69 73 20 73 | 70 65 63 69 66 69 65 64 |X * is s|pecified|
|00005a20| 20 62 79 20 74 68 65 20 | 63 65 6e 74 65 72 20 63 | by the |center c|
|00005a30| 6f 6f 72 64 69 6e 61 74 | 65 73 20 6f 66 20 69 74 |oordinat|es of it|
|00005a40| 73 20 66 69 72 73 74 20 | 63 65 6c 6c 2e 20 20 54 |s first |cell. T|
|00005a50| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 0a 58 20 2a |he numbe|r of.X *|
|00005a60| 20 63 61 6e 64 69 64 61 | 74 65 20 63 6f 6c 6f 72 | candida|te color|
|00005a70| 6d 61 70 20 65 6e 74 72 | 69 65 73 20 69 73 20 72 |map entr|ies is r|
|00005a80| 65 74 75 72 6e 65 64 2c | 20 61 6e 64 20 74 68 65 |eturned,| and the|
|00005a90| 69 72 20 63 6f 6c 6f 72 | 6d 61 70 20 69 6e 64 65 |ir color|map inde|
|00005aa0| 78 65 73 20 61 72 65 0a | 58 20 2a 20 70 6c 61 63 |xes are.|X * plac|
|00005ab0| 65 64 20 69 6e 20 63 6f | 6c 6f 72 6c 69 73 74 5b |ed in co|lorlist[|
|00005ac0| 5d 2e 0a 58 20 2a 20 54 | 68 69 73 20 72 6f 75 74 |]..X * T|his rout|
|00005ad0| 69 6e 65 20 75 73 65 73 | 20 48 65 63 6b 62 65 72 |ine uses| Heckber|
|00005ae0| 74 27 73 20 22 6c 6f 63 | 61 6c 6c 79 20 73 6f 72 |t's "loc|ally sor|
|00005af0| 74 65 64 20 73 65 61 72 | 63 68 22 20 63 72 69 74 |ted sear|ch" crit|
|00005b00| 65 72 69 6f 6e 20 74 6f | 20 73 65 6c 65 63 74 0a |erion to| select.|
|00005b10| 58 20 2a 20 74 68 65 20 | 63 6f 6c 6f 72 73 20 74 |X * the |colors t|
|00005b20| 68 61 74 20 6e 65 65 64 | 20 66 75 72 74 68 65 72 |hat need| further|
|00005b30| 20 63 6f 6e 73 69 64 65 | 72 61 74 69 6f 6e 2e 0a | conside|ration..|
|00005b40| 58 20 2a 2f 0a 58 7b 0a | 58 20 20 69 6e 74 20 6e |X */.X{.|X int n|
|00005b50| 75 6d 63 6f 6c 6f 72 73 | 20 3d 20 63 69 6e 66 6f |umcolors| = cinfo|
|00005b60| 2d 3e 61 63 74 75 61 6c | 5f 6e 75 6d 62 65 72 5f |->actual|_number_|
|00005b70| 6f 66 5f 63 6f 6c 6f 72 | 73 3b 0a 58 20 20 69 6e |of_color|s;.X in|
|00005b80| 74 20 6d 61 78 63 30 2c | 20 6d 61 78 63 31 2c 20 |t maxc0,| maxc1, |
|00005b90| 6d 61 78 63 32 3b 0a 58 | 20 20 69 6e 74 20 63 65 |maxc2;.X| int ce|
|00005ba0| 6e 74 65 72 63 30 2c 20 | 63 65 6e 74 65 72 63 31 |nterc0, |centerc1|
|00005bb0| 2c 20 63 65 6e 74 65 72 | 63 32 3b 0a 58 20 20 69 |, center|c2;.X i|
|00005bc0| 6e 74 20 69 2c 20 78 2c | 20 6e 63 6f 6c 6f 72 73 |nt i, x,| ncolors|
|00005bd0| 3b 0a 58 20 20 49 4e 54 | 33 32 20 6d 69 6e 6d 61 |;.X INT|32 minma|
|00005be0| 78 64 69 73 74 2c 20 6d | 69 6e 5f 64 69 73 74 2c |xdist, m|in_dist,|
|00005bf0| 20 6d 61 78 5f 64 69 73 | 74 2c 20 74 64 69 73 74 | max_dis|t, tdist|
|00005c00| 3b 0a 58 20 20 49 4e 54 | 33 32 20 6d 69 6e 64 69 |;.X INT|32 mindi|
|00005c10| 73 74 5b 4d 41 58 4e 55 | 4d 43 4f 4c 4f 52 53 5d |st[MAXNU|MCOLORS]|
|00005c20| 3b 09 2f 2a 20 6d 69 6e | 20 64 69 73 74 61 6e 63 |;./* min| distanc|
|00005c30| 65 20 74 6f 20 63 6f 6c | 6f 72 6d 61 70 20 65 6e |e to col|ormap en|
|00005c40| 74 72 79 20 69 20 2a 2f | 0a 58 0a 58 20 20 2f 2a |try i */|.X.X /*|
|00005c50| 20 43 6f 6d 70 75 74 65 | 20 74 72 75 65 20 63 6f | Compute| true co|
|00005c60| 6f 72 64 69 6e 61 74 65 | 73 20 6f 66 20 75 70 64 |ordinate|s of upd|
|00005c70| 61 74 65 20 62 6f 78 27 | 73 20 75 70 70 65 72 20 |ate box'|s upper |
|00005c80| 63 6f 72 6e 65 72 20 61 | 6e 64 20 63 65 6e 74 65 |corner a|nd cente|
|00005c90| 72 2e 0a 58 20 20 20 2a | 20 41 63 74 75 61 6c 6c |r..X *| Actuall|
|00005ca0| 79 20 77 65 20 63 6f 6d | 70 75 74 65 20 74 68 65 |y we com|pute the|
|00005cb0| 20 63 6f 6f 72 64 69 6e | 61 74 65 73 20 6f 66 20 | coordin|ates of |
|00005cc0| 74 68 65 20 63 65 6e 74 | 65 72 20 6f 66 20 74 68 |the cent|er of th|
|00005cd0| 65 20 75 70 70 65 72 2d | 63 6f 72 6e 65 72 0a 58 |e upper-|corner.X|
|00005ce0| 20 20 20 2a 20 68 69 73 | 74 6f 67 72 61 6d 20 63 | * his|togram c|
|00005cf0| 65 6c 6c 2c 20 77 68 69 | 63 68 20 61 72 65 20 74 |ell, whi|ch are t|
|00005d00| 68 65 20 75 70 70 65 72 | 20 62 6f 75 6e 64 73 20 |he upper| bounds |
|00005d10| 6f 66 20 74 68 65 20 76 | 6f 6c 75 6d 65 20 77 65 |of the v|olume we|
|00005d20| 20 63 61 72 65 20 61 62 | 6f 75 74 2e 0a 58 20 20 | care ab|out..X |
|00005d30| 20 2a 20 4e 6f 74 65 20 | 74 68 61 74 20 73 69 6e | * Note |that sin|
|00005d40| 63 65 20 22 3e 3e 22 20 | 72 6f 75 6e 64 73 20 64 |ce ">>" |rounds d|
|00005d50| 6f 77 6e 2c 20 74 68 65 | 20 22 63 65 6e 74 65 72 |own, the| "center|
|00005d60| 22 20 76 61 6c 75 65 73 | 20 6d 61 79 20 62 65 20 |" values| may be |
|00005d70| 63 6c 6f 73 65 72 20 74 | 6f 0a 58 20 20 20 2a 20 |closer t|o.X * |
|00005d80| 6d 69 6e 20 74 68 61 6e | 20 74 6f 20 6d 61 78 3b |min than| to max;|
|00005d90| 20 68 65 6e 63 65 20 63 | 6f 6d 70 61 72 69 73 6f | hence c|ompariso|
|00005da0| 6e 73 20 74 6f 20 74 68 | 65 6d 20 6d 75 73 74 20 |ns to th|em must |
|00005db0| 62 65 20 22 3c 3d 22 2c | 20 6e 6f 74 20 22 3c 22 |be "<=",| not "<"|
|00005dc0| 2e 0a 58 20 20 20 2a 2f | 0a 58 20 20 6d 61 78 63 |..X */|.X maxc|
|00005dd0| 30 20 3d 20 6d 69 6e 63 | 30 20 2b 20 28 28 31 20 |0 = minc|0 + ((1 |
|00005de0| 3c 3c 20 42 4f 58 5f 59 | 5f 53 48 49 46 54 29 20 |<< BOX_Y|_SHIFT) |
|00005df0| 2d 20 28 31 20 3c 3c 20 | 59 5f 53 48 49 46 54 29 |- (1 << |Y_SHIFT)|
|00005e00| 29 3b 0a 58 20 20 63 65 | 6e 74 65 72 63 30 20 3d |);.X ce|nterc0 =|
|00005e10| 20 28 6d 69 6e 63 30 20 | 2b 20 6d 61 78 63 30 29 | (minc0 |+ maxc0)|
|00005e20| 20 3e 3e 20 31 3b 0a 58 | 20 20 6d 61 78 63 31 20 | >> 1;.X| maxc1 |
|00005e30| 3d 20 6d 69 6e 63 31 20 | 2b 20 28 28 31 20 3c 3c |= minc1 |+ ((1 <<|
|00005e40| 20 42 4f 58 5f 43 5f 53 | 48 49 46 54 29 20 2d 20 | BOX_C_S|HIFT) - |
|00005e50| 28 31 20 3c 3c 20 43 5f | 53 48 49 46 54 29 29 3b |(1 << C_|SHIFT));|
|00005e60| 0a 58 20 20 63 65 6e 74 | 65 72 63 31 20 3d 20 28 |.X cent|erc1 = (|
|00005e70| 6d 69 6e 63 31 20 2b 20 | 6d 61 78 63 31 29 20 3e |minc1 + |maxc1) >|
|00005e80| 3e 20 31 3b 0a 58 20 20 | 6d 61 78 63 32 20 3d 20 |> 1;.X |maxc2 = |
|00005e90| 6d 69 6e 63 32 20 2b 20 | 28 28 31 20 3c 3c 20 42 |minc2 + |((1 << B|
|00005ea0| 4f 58 5f 43 5f 53 48 49 | 46 54 29 20 2d 20 28 31 |OX_C_SHI|FT) - (1|
|00005eb0| 20 3c 3c 20 43 5f 53 48 | 49 46 54 29 29 3b 0a 58 | << C_SH|IFT));.X|
|00005ec0| 20 20 63 65 6e 74 65 72 | 63 32 20 3d 20 28 6d 69 | center|c2 = (mi|
|00005ed0| 6e 63 32 20 2b 20 6d 61 | 78 63 32 29 20 3e 3e 20 |nc2 + ma|xc2) >> |
|00005ee0| 31 3b 0a 58 0a 58 20 20 | 2f 2a 20 46 6f 72 20 65 |1;.X.X |/* For e|
|00005ef0| 61 63 68 20 63 6f 6c 6f | 72 20 69 6e 20 63 6f 6c |ach colo|r in col|
|00005f00| 6f 72 6d 61 70 2c 20 66 | 69 6e 64 3a 0a 58 20 20 |ormap, f|ind:.X |
|00005f10| 20 2a 20 20 31 2e 20 69 | 74 73 20 6d 69 6e 69 6d | * 1. i|ts minim|
|00005f20| 75 6d 20 73 71 75 61 72 | 65 64 2d 64 69 73 74 61 |um squar|ed-dista|
|00005f30| 6e 63 65 20 74 6f 20 61 | 6e 79 20 70 6f 69 6e 74 |nce to a|ny point|
|00005f40| 20 69 6e 20 74 68 65 20 | 75 70 64 61 74 65 20 62 | in the |update b|
|00005f50| 6f 78 0a 58 20 20 20 2a | 20 20 20 20 20 28 7a 65 |ox.X *| (ze|
|00005f60| 72 6f 20 69 66 20 63 6f | 6c 6f 72 20 69 73 20 77 |ro if co|lor is w|
|00005f70| 69 74 68 69 6e 20 75 70 | 64 61 74 65 20 62 6f 78 |ithin up|date box|
|00005f80| 29 3b 0a 58 20 20 20 2a | 20 20 32 2e 20 69 74 73 |);.X *| 2. its|
|00005f90| 20 6d 61 78 69 6d 75 6d | 20 73 71 75 61 72 65 64 | maximum| squared|
|00005fa0| 2d 64 69 73 74 61 6e 63 | 65 20 74 6f 20 61 6e 79 |-distanc|e to any|
|00005fb0| 20 70 6f 69 6e 74 20 69 | 6e 20 74 68 65 20 75 70 | point i|n the up|
|00005fc0| 64 61 74 65 20 62 6f 78 | 2e 0a 58 20 20 20 2a 20 |date box|..X * |
|00005fd0| 42 6f 74 68 20 6f 66 20 | 74 68 65 73 65 20 63 61 |Both of |these ca|
|00005fe0| 6e 20 62 65 20 66 6f 75 | 6e 64 20 62 79 20 63 6f |n be fou|nd by co|
|00005ff0| 6e 73 69 64 65 72 69 6e | 67 20 6f 6e 6c 79 20 74 |nsiderin|g only t|
|00006000| 68 65 20 63 6f 72 6e 65 | 72 73 20 6f 66 20 74 68 |he corne|rs of th|
|00006010| 65 20 62 6f 78 2e 0a 58 | 20 20 20 2a 20 57 65 20 |e box..X| * We |
|00006020| 73 61 76 65 20 74 68 65 | 20 6d 69 6e 69 6d 75 6d |save the| minimum|
|00006030| 20 64 69 73 74 61 6e 63 | 65 20 66 6f 72 20 65 61 | distanc|e for ea|
|00006040| 63 68 20 63 6f 6c 6f 72 | 20 69 6e 20 6d 69 6e 64 |ch color| in mind|
|00006050| 69 73 74 5b 5d 3b 0a 58 | 20 20 20 2a 20 6f 6e 6c |ist[];.X| * onl|
|00006060| 79 20 74 68 65 20 73 6d | 61 6c 6c 65 73 74 20 6d |y the sm|allest m|
|00006070| 61 78 69 6d 75 6d 20 64 | 69 73 74 61 6e 63 65 20 |aximum d|istance |
|00006080| 69 73 20 6f 66 20 69 6e | 74 65 72 65 73 74 2e 0a |is of in|terest..|
|00006090| 58 20 20 20 2a 20 4e 6f | 74 65 20 77 65 20 68 61 |X * No|te we ha|
|000060a0| 76 65 20 74 6f 20 73 63 | 61 6c 65 20 59 20 74 6f |ve to sc|ale Y to|
|000060b0| 20 67 65 74 20 63 6f 72 | 72 65 63 74 20 64 69 73 | get cor|rect dis|
|000060c0| 74 61 6e 63 65 20 69 6e | 20 73 63 61 6c 65 64 20 |tance in| scaled |
|000060d0| 73 70 61 63 65 2e 0a 58 | 20 20 20 2a 2f 0a 58 20 |space..X| */.X |
|000060e0| 20 6d 69 6e 6d 61 78 64 | 69 73 74 20 3d 20 30 78 | minmaxd|ist = 0x|
|000060f0| 37 46 46 46 46 46 46 46 | 4c 3b 0a 58 0a 58 20 20 |7FFFFFFF|L;.X.X |
|00006100| 66 6f 72 20 28 69 20 3d | 20 30 3b 20 69 20 3c 20 |for (i =| 0; i < |
|00006110| 6e 75 6d 63 6f 6c 6f 72 | 73 3b 20 69 2b 2b 29 20 |numcolor|s; i++) |
|00006120| 7b 0a 58 20 20 20 20 2f | 2a 20 57 65 20 63 6f 6d |{.X /|* We com|
|00006130| 70 75 74 65 20 74 68 65 | 20 73 71 75 61 72 65 64 |pute the| squared|
|00006140| 2d 63 30 2d 64 69 73 74 | 61 6e 63 65 20 74 65 72 |-c0-dist|ance ter|
|00006150| 6d 2c 20 74 68 65 6e 20 | 61 64 64 20 69 6e 20 74 |m, then |add in t|
|00006160| 68 65 20 6f 74 68 65 72 | 20 74 77 6f 2e 20 2a 2f |he other| two. */|
|00006170| 0a 58 20 20 20 20 78 20 | 3d 20 47 45 54 4a 53 41 |.X x |= GETJSA|
|00006180| 4d 50 4c 45 28 6d 79 5f | 63 6f 6c 6f 72 6d 61 70 |MPLE(my_|colormap|
|00006190| 5b 30 5d 5b 69 5d 29 3b | 0a 58 20 20 20 20 69 66 |[0][i]);|.X if|
|000061a0| 20 28 78 20 3c 20 6d 69 | 6e 63 30 29 20 7b 0a 58 | (x < mi|nc0) {.X|
|000061b0| 20 20 20 20 20 20 74 64 | 69 73 74 20 3d 20 28 78 | td|ist = (x|
|000061c0| 20 2d 20 6d 69 6e 63 30 | 29 20 2a 20 59 5f 53 43 | - minc0|) * Y_SC|
|000061d0| 41 4c 45 3b 0a 58 20 20 | 20 20 20 20 6d 69 6e 5f |ALE;.X | min_|
|000061e0| 64 69 73 74 20 3d 20 74 | 64 69 73 74 2a 74 64 69 |dist = t|dist*tdi|
|000061f0| 73 74 3b 0a 58 20 20 20 | 20 20 20 74 64 69 73 74 |st;.X | tdist|
|00006200| 20 3d 20 28 78 20 2d 20 | 6d 61 78 63 30 29 20 2a | = (x - |maxc0) *|
|00006210| 20 59 5f 53 43 41 4c 45 | 3b 0a 58 20 20 20 20 20 | Y_SCALE|;.X |
|00006220| 20 6d 61 78 5f 64 69 73 | 74 20 3d 20 74 64 69 73 | max_dis|t = tdis|
|00006230| 74 2a 74 64 69 73 74 3b | 0a 58 20 20 20 20 7d 20 |t*tdist;|.X } |
|00006240| 65 6c 73 65 20 69 66 20 | 28 78 20 3e 20 6d 61 78 |else if |(x > max|
|00006250| 63 30 29 20 7b 0a 58 20 | 20 20 20 20 20 74 64 69 |c0) {.X | tdi|
|00006260| 73 74 20 3d 20 28 78 20 | 2d 20 6d 61 78 63 30 29 |st = (x |- maxc0)|
|00006270| 20 2a 20 59 5f 53 43 41 | 4c 45 3b 0a 58 20 20 20 | * Y_SCA|LE;.X |
|00006280| 20 20 20 6d 69 6e 5f 64 | 69 73 74 20 3d 20 74 64 | min_d|ist = td|
|00006290| 69 73 74 2a 74 64 69 73 | 74 3b 0a 58 20 20 20 20 |ist*tdis|t;.X |
|000062a0| 20 20 74 64 69 73 74 20 | 3d 20 28 78 20 2d 20 6d | tdist |= (x - m|
|000062b0| 69 6e 63 30 29 20 2a 20 | 59 5f 53 43 41 4c 45 3b |inc0) * |Y_SCALE;|
|000062c0| 0a 58 20 20 20 20 20 20 | 6d 61 78 5f 64 69 73 74 |.X |max_dist|
|000062d0| 20 3d 20 74 64 69 73 74 | 2a 74 64 69 73 74 3b 0a | = tdist|*tdist;.|
|000062e0| 58 20 20 20 20 7d 20 65 | 6c 73 65 20 7b 0a 58 20 |X } e|lse {.X |
|000062f0| 20 20 20 20 20 2f 2a 20 | 77 69 74 68 69 6e 20 63 | /* |within c|
|00006300| 65 6c 6c 20 72 61 6e 67 | 65 20 73 6f 20 6e 6f 20 |ell rang|e so no |
|00006310| 63 6f 6e 74 72 69 62 75 | 74 69 6f 6e 20 74 6f 20 |contribu|tion to |
|00006320| 6d 69 6e 5f 64 69 73 74 | 20 2a 2f 0a 58 20 20 20 |min_dist| */.X |
|00006330| 20 20 20 6d 69 6e 5f 64 | 69 73 74 20 3d 20 30 3b | min_d|ist = 0;|
|00006340| 0a 58 20 20 20 20 20 20 | 69 66 20 28 78 20 3c 3d |.X |if (x <=|
|00006350| 20 63 65 6e 74 65 72 63 | 30 29 20 7b 0a 58 09 74 | centerc|0) {.X.t|
|00006360| 64 69 73 74 20 3d 20 28 | 78 20 2d 20 6d 61 78 63 |dist = (|x - maxc|
|00006370| 30 29 20 2a 20 59 5f 53 | 43 41 4c 45 3b 0a 58 09 |0) * Y_S|CALE;.X.|
|00006380| 6d 61 78 5f 64 69 73 74 | 20 3d 20 74 64 69 73 74 |max_dist| = tdist|
|00006390| 2a 74 64 69 73 74 3b 0a | 58 20 20 20 20 20 20 7d |*tdist;.|X }|
|000063a0| 20 65 6c 73 65 20 7b 0a | 58 09 74 64 69 73 74 20 | else {.|X.tdist |
|000063b0| 3d 20 28 78 20 2d 20 6d | 69 6e 63 30 29 20 2a 20 |= (x - m|inc0) * |
|000063c0| 59 5f 53 43 41 4c 45 3b | 0a 58 09 6d 61 78 5f 64 |Y_SCALE;|.X.max_d|
|000063d0| 69 73 74 20 3d 20 74 64 | 69 73 74 2a 74 64 69 73 |ist = td|ist*tdis|
|000063e0| 74 3b 0a 58 20 20 20 20 | 20 20 7d 0a 58 20 20 20 |t;.X | }.X |
|000063f0| 20 7d 0a 58 0a 58 20 20 | 20 20 78 20 3d 20 47 45 | }.X.X | x = GE|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
