Mercurial > hg > xemacs-beta
annotate src/imgproc.c @ 2367:ecf1ebac70d8
[xemacs-hg @ 2004-11-04 23:05:23 by ben]
commit mega-patch
configure.in: Turn off -Winline and -Wchar-subscripts.
Use the right set of cflags when compiling modules.
Rewrite ldap configuration to separate the inclusion of lber
(needed in recent Cygwin) from the basic checks for the
needed libraries.
add a function for MAKE_JUNK_C; initially code was added to
generate xemacs.def using this, but it will need to be rewritten.
add an rm -f for junk.c to avoid weird Cygwin bug with cp -f onto
an existing file.
Sort list of auto-detected functions and eliminate unused checks for
stpcpy, setlocale and getwd.
Add autodetection of Cygwin scanf problems
BETA: Rewrite section on configure to indicate what flags are important
and what not.
digest-doc.c, make-dump-id.c, profile.c, sorted-doc.c: Add proper decls for main().
make-msgfile.c: Document that this is old junk.
Move proposal to text.c.
make-msgfile.lex: Move proposal to text.c.
make-mswin-unicode.pl: Convert error-generating code so that the entire message will
be seen as a single unrecognized token.
mule/mule-ccl.el: Update docs.
lispref/mule.texi: Update CCL docs.
ldap/eldap.c: Mule-ize.
Use EXTERNAL_LIST_LOOP_2 instead of deleted EXTERNAL_LIST_LOOP.
* XEmacs 21.5.18 "chestnut" is released.
---------------------------------------------------------------
MULE-RELATED WORK:
---------------------------------------------------------------
---------------------------
byte-char conversion
---------------------------
buffer.c, buffer.h, insdel.c, text.c: Port FSF algorithm for byte-char conversion, replacing broken
previous version. Track the char position of the gap. Add
functions to do char-byte conversion downwards as well as upwards.
Move comments about algorithm workings to internals manual.
---------------------------
work on types
---------------------------
alloc.c, console-x-impl.h, dump-data.c, dump-data.h, dumper.c, dialog-msw.c, dired-msw.c, doc.c, editfns.c, esd.c, event-gtk.h, event-msw.c, events.c, file-coding.c, file-coding.h, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-shared.c, glyphs-x.c, glyphs.c, glyphs.h, gui.c, hpplay.c, imgproc.c, intl-win32.c, lrecord.h, lstream.c, keymap.c, lisp.h, libsst.c, linuxplay.c, miscplay.c, miscplay.h, mule-coding.c, nas.c, nt.c, ntheap.c, ntplay.c, objects-msw.c, objects-tty.c, objects-x.c, print.c, process-nt.c, process.c, redisplay.h, select-common.h, select-gtk.c, select-x.c, sgiplay.c, sound.c, sound.h, sunplay.c, sysfile.h, sysdep.c, syswindows.h, text.c, unexnt.c, win32.c, xgccache.c: Further work on types. This creates a full set of types for all
the basic semantics of `char' that I have so far identified, so that
its semantics can always be identified for the purposes of proper
Mule-safe code, and the raw use of `char' always avoided.
(1) More type renaming, for consistency of naming.
Char_ASCII -> Ascbyte
UChar_ASCII -> UAscbyte
Char_Binary -> CBinbyte
UChar_Binary -> Binbyte
SChar_Binary -> SBinbyte
(2) Introduce Rawbyte, CRawbyte, Boolbyte, Chbyte, UChbyte, and
Bitbyte and use them.
(3) New types Itext, Wexttext and Textcount for separating out
the concepts of bytes and textual units (different under UTF-16
and UTF-32, which are potential internal encodings).
(4) qxestr*_c -> qxestr*_ascii.
lisp.h: New; goes with other qxe() functions. #### Maybe goes in a
different section.
lisp.h: Group generic int-type defs together with EMACS_INT defs.
lisp.h: * lisp.h (WEXTTEXT_IS_WIDE)
New defns.
lisp.h: New type to replace places where int occurs as a boolean.
It's signed because occasionally people may want to use -1 as
an error value, and because unsigned ints are viral -- see comments
in the internals manual against using them.
dynarr.c: int -> Bytecount.
---------------------------
Mule-izing
---------------------------
device-x.c: Partially Mule-ize.
dumper.c, dumper.h: Mule-ize. Use Rawbyte. Use stderr_out not printf. Use wext_*().
sysdep.c, syswindows.h, text.c: New Wexttext API for manipulation of external text that may be
Unicode (e.g. startup code under Windows).
emacs.c: Mule-ize. Properly deal with argv in external encoding.
Use wext_*() and Wexttext. Use Rawbyte.
#if 0 some old junk on SCO that is unlikely to be correct.
Rewrite allocation code in run-temacs.
emacs.c, symsinit.h, win32.c: Rename win32 init function and call it even earlier, to
initialize mswindows_9x_p even earlier, for use in startup code
(XEUNICODE_P).
process.c: Use _wenviron not environ under Windows, to get Unicode environment
variables.
event-Xt.c: Mule-ize drag-n-drop related stuff.
dragdrop.c, dragdrop.h, frame-x.c: Mule-ize.
text.h: Add some more stand-in defines for particular kinds of conversion;
use in Mule-ization work in frame-x.c etc.
---------------------------
Freshening
---------------------------
intl-auto-encap-win32.c, intl-auto-encap-win32.h: Regenerate.
---------------------------
Unicode-work
---------------------------
intl-win32.c, syswindows.h: Factor out common options to MultiByteToWideChar and
WideCharToMultiByte. Add convert_unicode_to_multibyte_malloc()
and convert_unicode_to_multibyte_dynarr() and use. Add stuff for
alloca() conversion of multibyte/unicode.
alloc.c: Use dfc_external_data_len() in case of unicode coding system.
alloc.c, mule-charset.c: Don't zero out and reinit charset Unicode tables. This fucks up
dump-time loading. Anyway, either we load them at dump time or
run time, never both.
unicode.c: Dump the blank tables as well.
---------------------------------------------------------------
DOCUMENTATION, MOSTLY MULE-RELATED:
---------------------------------------------------------------
EmacsFrame.c, emodules.c, event-Xt.c, fileio.c, input-method-xlib.c, mule-wnnfns.c, redisplay-gtk.c, redisplay-tty.c, redisplay-x.c, regex.c, sysdep.c: Add comment about Mule work needed.
text.h: Add more documentation describing why DFC routines were not written
to return their value. Add some other DFC documentation.
console-msw.c, console-msw.h: Add pointer to docs in win32.c.
emacs.c: Add comments on sources of doc info.
text.c, charset.h, unicode.c, intl-win32.c, intl-encap-win32.c, text.h, file-coding.c, mule-coding.c: Collect background comments and related to text matters and
internationalization, and proposals for work to be done, in text.c
or Internals manual, stuff related to specific textual API's in
text.h, and stuff related to internal implementation of Unicode
conversion in unicode.c. Put lots of pointers to the comments to
make them easier to find.
s/mingw32.h, s/win32-common.h, s/win32-native.h, s/windowsnt.h, win32.c: Add bunches of new documentation on the different kinds of
builds and environments under Windows and how they work.
Collect this info in win32.c. Add pointers to these docs in
the relevant s/* files.
emacs.c: Document places with long comments.
Remove comment about exiting, move to internals manual, put
in pointer.
event-stream.c: Move docs about event queues and focus to internals manual, put
in pointer.
events.h: Move docs about event stream callbacks to internals manual, put
in pointer.
profile.c, redisplay.c, signal.c: Move documentation to the Internals manual.
process-nt.c: Add pointer to comment in win32-native.el.
lisp.h: Add comments about some comment conventions.
lisp.h: Add comment about the second argument.
device-msw.c, redisplay-msw.c: @@#### comments are out-of-date.
---------------------------------------------------------------
PDUMP WORK (MOTIVATED BY UNICODE CHANGES)
---------------------------------------------------------------
alloc.c, buffer.c, bytecode.c, console-impl.h, console.c, device.c, dumper.c, lrecord.h, elhash.c, emodules.h, events.c, extents.c, frame.c, glyphs.c, glyphs.h, mule-charset.c, mule-coding.c, objects.c, profile.c, rangetab.c, redisplay.c, specifier.c, specifier.h, window.c, lstream.c, file-coding.h, file-coding.c: PDUMP:
Properly implement dump_add_root_block(), which never worked before,
and is necessary for dumping Unicode tables.
Pdump name changes for accuracy:
XD_STRUCT_PTR -> XD_BLOCK_PTR.
XD_STRUCT_ARRAY -> XD_BLOCK_ARRAY.
XD_C_STRING -> XD_ASCII_STRING.
*_structure_* -> *_block_*.
lrecord.h: some comments added about
dump_add_root_block() vs dump_add_root_block_ptr().
extents.c: remove incorrect comment about pdump problems with gap array.
---------------------------------------------------------------
ALLOCATION
---------------------------------------------------------------
abbrev.c, alloc.c, bytecode.c, casefiddle.c, device-msw.c, device-x.c, dired-msw.c, doc.c, doprnt.c, dragdrop.c, editfns.c, emodules.c, file-coding.c, fileio.c, filelock.c, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-x.c, gui-msw.c, gui-x.c, imgproc.c, intl-win32.c, lread.c, menubar-gtk.c, menubar.c, nt.c, objects-msw.c, objects-x.c, print.c, process-nt.c, process-unix.c, process.c, realpath.c, redisplay.c, search.c, select-common.c, symbols.c, sysdep.c, syswindows.h, text.c, text.h, ui-byhand.c: New macros {alloca,xnew}_{itext,{i,ext,raw,bin,asc}bytes} for
more convenient allocation of these commonly requested items.
Modify functions to use alloca_ibytes, alloca_array, alloca_extbytes,
xnew_ibytes, etc. also XREALLOC_ARRAY, xnew.
alloc.c: Rewrite the allocation functions to factor out repeated code.
Add assertions for freeing dumped data.
lisp.h: Moved down and consolidated with other allocation stuff.
lisp.h, dynarr.c: New functions for allocation that's very efficient when mostly in
LIFO order.
lisp.h, text.c, text.h: Factor out some stuff for general use by alloca()-conversion funs.
text.h, lisp.h: Fill out convenience routines for allocating various kinds of
bytes and put them in lisp.h. Use them in place of xmalloc(),
ALLOCA().
text.h: Fill out the convenience functions so the _MALLOC() kinds match
the alloca() kinds.
---------------------------------------------------------------
ERROR-CHECKING
---------------------------------------------------------------
text.h: Create ASSERT_ASCTEXT_ASCII() and ASSERT_ASCTEXT_ASCII_LEN()
from similar Eistring checkers and change the Eistring checkers to
use them instead.
---------------------------------------------------------------
MACROS IN LISP.H
---------------------------------------------------------------
lisp.h: Redo GCPRO declarations. Create a "base" set of functions that can
be used to generate any kind of gcpro sets -- regular, ngcpro,
nngcpro, private ones used in GC_EXTERNAL_LIST_LOOP_2.
buffer.c, callint.c, chartab.c, console-msw.c, device-x.c, dialog-msw.c, dired.c, extents.c, ui-gtk.c, rangetab.c, nt.c, mule-coding.c, minibuf.c, menubar-msw.c, menubar.c, menubar-gtk.c, lread.c, lisp.h, gutter.c, glyphs.c, glyphs-widget.c, fns.c, fileio.c, file-coding.c, specifier.c: Eliminate EXTERNAL_LIST_LOOP, which does not check for circularities.
Use EXTERNAL_LIST_LOOP_2 instead or EXTERNAL_LIST_LOOP_3
or EXTERNAL_PROPERTY_LIST_LOOP_3 or GC_EXTERNAL_LIST_LOOP_2
(new macro). Removed/redid comments on EXTERNAL_LIST_LOOP.
---------------------------------------------------------------
SPACING FIXES
---------------------------------------------------------------
callint.c, hftctl.c, number-gmp.c, process-unix.c: Spacing fixes.
---------------------------------------------------------------
FIX FOR GEOMETRY PROBLEM IN FIRST FRAME
---------------------------------------------------------------
unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by
release 1.5.12 of Cygwin].
toolbar.c: bug fix for problem of initial frame being 77 chars wide on Windows.
will be overridden by my other ws.
---------------------------------------------------------------
FIX FOR LEAKING PROCESS HANDLES:
---------------------------------------------------------------
process-nt.c: Fixes for leaking handles. Inspired by work done by Adrian Aichner
<adrian@xemacs.org>.
---------------------------------------------------------------
FIX FOR CYGWIN BUG (Unicode-related):
---------------------------------------------------------------
unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by
release 1.5.12 of Cygwin].
---------------------------------------------------------------
WARNING FIXES:
---------------------------------------------------------------
console-stream.c: `reinit' is unused.
compiler.h, event-msw.c, frame-msw.c, intl-encap-win32.c, text.h: Add stuff to deal with ANSI-aliasing warnings I got.
regex.c: Gather includes together to avoid warning.
---------------------------------------------------------------
CHANGES TO INITIALIZATION ROUTINES:
---------------------------------------------------------------
buffer.c, emacs.c, console.c, debug.c, device-x.c, device.c, dragdrop.c, emodules.c, eval.c, event-Xt.c, event-gtk.c, event-msw.c, event-stream.c, event-tty.c, events.c, extents.c, faces.c, file-coding.c, fileio.c, font-lock.c, frame-msw.c, glyphs-widget.c, glyphs.c, gui-x.c, insdel.c, lread.c, lstream.c, menubar-gtk.c, menubar-x.c, minibuf.c, mule-wnnfns.c, objects-msw.c, objects.c, print.c, scrollbar-x.c, search.c, select-x.c, text.c, undo.c, unicode.c, window.c, symsinit.h: Call reinit_*() functions directly from emacs.c, for clarity.
Factor out some redundant init code. Move disallowed stuff
that had crept into vars_of_glyphs() into complex_vars_of_glyphs().
Call init_eval_semi_early() from eval.c not in the middle of
vars_of_() in emacs.c since there should be no order dependency
in the latter calls.
---------------------------------------------------------------
ARMAGEDDON:
---------------------------------------------------------------
alloc.c, emacs.c, lisp.h, print.c: Rename inhibit_non_essential_printing_operations to
inhibit_non_essential_conversion_operations.
text.c: Assert on !inhibit_non_essential_conversion_operations.
console-msw.c, print.c: Don't do conversion in SetConsoleTitle or FindWindow to avoid
problems during armageddon. Put #errors for NON_ASCII_INTERNAL_FORMAT
in places where problems would arise.
---------------------------------------------------------------
CHANGES TO THE BUILD PROCEDURE:
---------------------------------------------------------------
config.h.in, s/cxux.h, s/usg5-4-2.h, m/powerpc.h: Add comment about correct ordering of this file.
Rearrange everything to follow this -- put all #undefs together
and before the s&m files. Add undefs for HAVE_ALLOCA, C_ALLOCA,
BROKEN_ALLOCA_IN_FUNCTION_CALLS, STACK_DIRECTION. Remove unused
HAVE_STPCPY, HAVE_GETWD, HAVE_SETLOCALE.
m/gec63.h: Deleted; totally broken, not used at all, not in FSF.
m/7300.h, m/acorn.h, m/alliant-2800.h, m/alliant.h, m/altos.h, m/amdahl.h, m/apollo.h, m/att3b.h, m/aviion.h, m/celerity.h, m/clipper.h, m/cnvrgnt.h, m/convex.h, m/cydra5.h, m/delta.h, m/delta88k.h, m/dpx2.h, m/elxsi.h, m/ews4800r.h, m/gould.h, m/hp300bsd.h, m/hp800.h, m/hp9000s300.h, m/i860.h, m/ibmps2-aix.h, m/ibmrs6000.h, m/ibmrt-aix.h, m/ibmrt.h, m/intel386.h, m/iris4d.h, m/iris5d.h, m/iris6d.h, m/irist.h, m/isi-ov.h, m/luna88k.h, m/m68k.h, m/masscomp.h, m/mg1.h, m/mips-nec.h, m/mips-siemens.h, m/mips.h, m/news.h, m/nh3000.h, m/nh4000.h, m/ns32000.h, m/orion105.h, m/pfa50.h, m/plexus.h, m/pmax.h, m/powerpc.h, m/pyrmips.h, m/sequent-ptx.h, m/sequent.h, m/sgi-challenge.h, m/symmetry.h, m/tad68k.h, m/tahoe.h, m/targon31.h, m/tekxd88.h, m/template.h, m/tower32.h, m/tower32v3.h, m/ustation.h, m/vax.h, m/wicat.h, m/xps100.h: Delete C_ALLOCA, HAVE_ALLOCA, STACK_DIRECTION,
BROKEN_ALLOCA_IN_FUNCTION_CALLS. All of this is auto-detected.
When in doubt, I followed recent FSF sources, which also have
these things deleted.
author | ben |
---|---|
date | Thu, 04 Nov 2004 23:08:28 +0000 |
parents | a8d8f419b459 |
children | facf3239ba30 |
rev | line source |
---|---|
428 | 1 /* Image processing functions |
2 Copyright (C) 1998 Jareth Hein | |
3 | |
4 This file is a part of XEmacs | |
5 | |
6 XEmacs is free software; you can redistribute it and/or modify it | |
7 under the terms of the GNU General Public License as published by the | |
8 Free Software Foundation; either version 2, or (at your option) any | |
9 later version. | |
10 | |
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT | |
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with XEmacs; see the file COPYING. If not, write to | |
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 Boston, MA 02111-1307, USA. */ | |
20 | |
21 /* Synched up with: Not in FSF. */ | |
22 | |
23 /* Original author: Jareth Hein */ | |
24 | |
25 /* Parts of this file are based on code from Sam Leffler's tiff library, | |
26 with the original copyright displayed here: | |
27 | |
28 Copyright (c) 1988-1997 Sam Leffler | |
29 Copyright (c) 1991-1997 Silicon Graphics, Inc. | |
30 | |
31 Permission to use, copy, modify, distribute, and sell this software and | |
32 its documentation for any purpose is hereby granted without fee, provided | |
33 that (i) the above copyright notices and this permission notice appear in | |
34 all copies of the software and related documentation, and (ii) the names of | |
35 Sam Leffler and Silicon Graphics may not be used in any advertising or | |
36 publicity relating to the software without the specific, prior written | |
37 permission of Sam Leffler and Silicon Graphics. */ | |
38 | |
39 /* Quantizing code based off of the paper | |
40 Color Image Quantization for Frame Buffer Display, Paul Heckbert, | |
41 Siggraph '82 proceedings, pp. 297-307 */ | |
42 | |
43 #include <config.h> | |
44 #include "lisp.h" | |
45 #include "imgproc.h" | |
46 | |
47 static void | |
2367 | 48 get_histogram(quant_table *qt, Binbyte *pic, |
428 | 49 int width, int height, Colorbox* box) |
50 { | |
2367 | 51 register Binbyte *inptr; |
428 | 52 register int red, green, blue; |
647 | 53 register int j, i; |
428 | 54 |
55 box->rmin = box->gmin = box->bmin = 999; | |
56 box->rmax = box->gmax = box->bmax = -1; | |
57 box->total = width * height; | |
58 | |
59 inptr = pic; | |
60 for (i = 0; i < height; i++) | |
61 { | |
62 for (j = width; j-- > 0;) | |
63 { | |
64 red = *inptr++ >> COLOR_SHIFT; | |
65 green = *inptr++ >> COLOR_SHIFT; | |
66 blue = *inptr++ >> COLOR_SHIFT; | |
67 if (red < box->rmin) | |
68 box->rmin = red; | |
69 if (red > box->rmax) | |
70 box->rmax = red; | |
71 if (green < box->gmin) | |
72 box->gmin = green; | |
73 if (green > box->gmax) | |
74 box->gmax = green; | |
75 if (blue < box->bmin) | |
76 box->bmin = blue; | |
77 if (blue > box->bmax) | |
78 box->bmax = blue; | |
79 qt->histogram[red][green][blue]++; | |
80 } | |
81 } | |
82 } | |
83 | |
84 static Colorbox * | |
85 largest_box(quant_table *qt) | |
86 { | |
87 register Colorbox *p, *b; | |
88 register int size; | |
89 | |
90 b = NULL; | |
91 size = -1; | |
92 for (p = qt->usedboxes; p != NULL; p = p->next) | |
93 if ((p->rmax > p->rmin || p->gmax > p->gmin || | |
94 p->bmax > p->bmin) && p->total > size) | |
95 size = (b = p)->total; | |
96 return (b); | |
97 } | |
98 | |
99 static void | |
100 shrinkbox(quant_table *qt, Colorbox* box) | |
101 { | |
102 register int *histp, ir, ig, ib; | |
103 | |
104 if (box->rmax > box->rmin) | |
105 { | |
106 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
107 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
108 { | |
109 histp = &(qt->histogram[ir][ig][box->bmin]); | |
110 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
111 if (*histp++ != 0) | |
112 { | |
113 box->rmin = ir; | |
114 goto have_rmin; | |
115 } | |
116 } | |
117 have_rmin: | |
118 if (box->rmax > box->rmin) | |
119 for (ir = box->rmax; ir >= box->rmin; --ir) | |
120 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
121 { | |
122 histp = &(qt->histogram[ir][ig][box->bmin]); | |
123 ib = box->bmin; | |
124 for (; ib <= box->bmax; ++ib) | |
125 if (*histp++ != 0) | |
126 { | |
127 box->rmax = ir; | |
128 goto have_rmax; | |
129 } | |
130 } | |
131 } | |
132 have_rmax: | |
133 if (box->gmax > box->gmin) | |
134 { | |
135 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
136 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
137 { | |
138 histp = &(qt->histogram[ir][ig][box->bmin]); | |
139 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
140 if (*histp++ != 0) | |
141 { | |
142 box->gmin = ig; | |
143 goto have_gmin; | |
144 } | |
145 } | |
146 have_gmin: | |
147 if (box->gmax > box->gmin) | |
148 for (ig = box->gmax; ig >= box->gmin; --ig) | |
149 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
150 { | |
151 histp = &(qt->histogram[ir][ig][box->bmin]); | |
152 ib = box->bmin; | |
153 for (; ib <= box->bmax; ++ib) | |
154 if (*histp++ != 0) | |
155 { | |
156 box->gmax = ig; | |
157 goto have_gmax; | |
158 } | |
159 } | |
160 } | |
161 have_gmax: | |
162 if (box->bmax > box->bmin) | |
163 { | |
164 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
165 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
166 { | |
167 histp = &(qt->histogram[ir][box->gmin][ib]); | |
168 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
169 { | |
170 if (*histp != 0) | |
171 { | |
172 box->bmin = ib; | |
173 goto have_bmin; | |
174 } | |
175 histp += B_LEN; | |
176 } | |
177 } | |
178 have_bmin: | |
179 if (box->bmax > box->bmin) | |
180 for (ib = box->bmax; ib >= box->bmin; --ib) | |
181 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
182 { | |
183 histp = &(qt->histogram[ir][box->gmin][ib]); | |
184 ig = box->gmin; | |
185 for (; ig <= box->gmax; ++ig) | |
186 { | |
187 if (*histp != 0) | |
188 { | |
189 box->bmax = ib; | |
190 goto have_bmax; | |
191 } | |
192 histp += B_LEN; | |
193 } | |
194 } | |
195 } | |
196 have_bmax: | |
197 ; | |
198 } | |
199 | |
200 static void | |
201 splitbox(quant_table *qt, Colorbox* ptr) | |
202 { | |
203 int hist2[B_LEN]; | |
204 int first = 0, last = 0; | |
205 register Colorbox *new; | |
206 register int *iptr, *histp; | |
207 register int i, j; | |
208 register int ir,ig,ib; | |
209 register int sum, sum1, sum2; | |
210 enum { RED, GREEN, BLUE } axis; | |
211 | |
212 /* | |
213 * See which axis is the largest, do a histogram along that | |
214 * axis. Split at median point. Contract both new boxes to | |
215 * fit points and return | |
216 */ | |
217 i = ptr->rmax - ptr->rmin; | |
218 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin) | |
219 axis = RED; | |
220 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin) | |
221 axis = GREEN; | |
222 else | |
223 axis = BLUE; | |
224 /* get histogram along longest axis */ | |
225 switch (axis) | |
226 { | |
227 case RED: | |
228 histp = &hist2[ptr->rmin]; | |
229 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
230 { | |
231 *histp = 0; | |
232 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
233 { | |
234 iptr = &(qt->histogram[ir][ig][ptr->bmin]); | |
235 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
236 *histp += *iptr++; | |
237 } | |
238 histp++; | |
239 } | |
240 first = ptr->rmin; | |
241 last = ptr->rmax; | |
242 break; | |
243 case GREEN: | |
244 histp = &hist2[ptr->gmin]; | |
245 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
246 { | |
247 *histp = 0; | |
248 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
249 { | |
250 iptr = &(qt->histogram[ir][ig][ptr->bmin]); | |
251 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
252 *histp += *iptr++; | |
253 } | |
254 histp++; | |
255 } | |
256 first = ptr->gmin; | |
257 last = ptr->gmax; | |
258 break; | |
259 case BLUE: | |
260 histp = &hist2[ptr->bmin]; | |
261 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
262 { | |
263 *histp = 0; | |
264 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
265 { | |
266 iptr = &(qt->histogram[ir][ptr->gmin][ib]); | |
267 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
268 { | |
269 *histp += *iptr; | |
270 iptr += B_LEN; | |
271 } | |
272 } | |
273 histp++; | |
274 } | |
275 first = ptr->bmin; | |
276 last = ptr->bmax; | |
277 break; | |
278 } | |
279 /* find median point */ | |
280 sum2 = ptr->total / 2; | |
281 histp = &hist2[first]; | |
282 sum = 0; | |
283 for (i = first; i <= last && (sum += *histp++) < sum2; ++i) | |
284 ; | |
285 if (i == first) | |
286 i++; | |
287 | |
288 /* Create new box, re-allocate points */ | |
289 new = qt->freeboxes; | |
290 qt->freeboxes = new->next; | |
291 if (qt->freeboxes) | |
292 qt->freeboxes->prev = NULL; | |
293 if (qt->usedboxes) | |
294 qt->usedboxes->prev = new; | |
295 new->next = qt->usedboxes; | |
296 qt->usedboxes = new; | |
297 | |
298 histp = &hist2[first]; | |
299 for (sum1 = 0, j = first; j < i; j++) | |
300 sum1 += *histp++; | |
301 for (sum2 = 0, j = i; j <= last; j++) | |
302 sum2 += *histp++; | |
303 new->total = sum1; | |
304 ptr->total = sum2; | |
305 | |
306 new->rmin = ptr->rmin; | |
307 new->rmax = ptr->rmax; | |
308 new->gmin = ptr->gmin; | |
309 new->gmax = ptr->gmax; | |
310 new->bmin = ptr->bmin; | |
311 new->bmax = ptr->bmax; | |
312 switch (axis) | |
313 { | |
314 case RED: | |
315 new->rmax = i-1; | |
316 ptr->rmin = i; | |
317 break; | |
318 case GREEN: | |
319 new->gmax = i-1; | |
320 ptr->gmin = i; | |
321 break; | |
322 case BLUE: | |
323 new->bmax = i-1; | |
324 ptr->bmin = i; | |
325 break; | |
326 } | |
327 shrinkbox (qt, new); | |
328 shrinkbox (qt, ptr); | |
329 } | |
330 | |
331 | |
332 static C_cell * | |
333 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue) | |
334 { | |
335 register int ir, ig, ib, i; | |
336 register C_cell *ptr; | |
337 int mindist, next_n; | |
338 register int tmp, dist, n; | |
339 | |
340 ir = red >> (COLOR_DEPTH-C_DEPTH); | |
341 ig = green >> (COLOR_DEPTH-C_DEPTH); | |
342 ib = blue >> (COLOR_DEPTH-C_DEPTH); | |
2367 | 343 ptr = xnew (C_cell); |
428 | 344 *(qt->ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr; |
345 ptr->num_ents = 0; | |
346 | |
347 /* | |
348 * Step 1: find all colors inside this cell, while we're at | |
349 * it, find distance of centermost point to furthest corner | |
350 */ | |
351 mindist = 99999999; | |
352 for (i = 0; i < num_colors; ++i) | |
353 { | |
354 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || | |
355 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || | |
356 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) | |
357 continue; | |
358 ptr->entries[ptr->num_ents][0] = i; | |
359 ptr->entries[ptr->num_ents][1] = 0; | |
360 ++ptr->num_ents; | |
361 tmp = qt->rm[i] - red; | |
362 if (tmp < (MAX_COLOR/C_LEN/2)) | |
363 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
364 dist = tmp*tmp; | |
365 tmp = qt->gm[i] - green; | |
366 if (tmp < (MAX_COLOR/C_LEN/2)) | |
367 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
368 dist += tmp*tmp; | |
369 tmp = qt->bm[i] - blue; | |
370 if (tmp < (MAX_COLOR/C_LEN/2)) | |
371 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
372 dist += tmp*tmp; | |
373 if (dist < mindist) | |
374 mindist = dist; | |
375 } | |
376 | |
377 /* | |
378 * Step 3: find all points within that distance to cell. | |
379 */ | |
380 for (i = 0; i < num_colors; ++i) | |
381 { | |
382 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && | |
383 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && | |
384 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) | |
385 continue; | |
386 dist = 0; | |
387 if ((tmp = red - qt->rm[i]) > 0 || | |
388 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) | |
389 dist += tmp*tmp; | |
390 if ((tmp = green - qt->gm[i]) > 0 || | |
391 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) | |
392 dist += tmp*tmp; | |
393 if ((tmp = blue - qt->bm[i]) > 0 || | |
394 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 ) | |
395 dist += tmp*tmp; | |
396 if (dist < mindist) | |
397 { | |
398 ptr->entries[ptr->num_ents][0] = i; | |
399 ptr->entries[ptr->num_ents][1] = dist; | |
400 ++ptr->num_ents; | |
401 } | |
402 } | |
403 | |
404 /* | |
405 * Sort color cells by distance, use cheap exchange sort | |
406 */ | |
407 for (n = ptr->num_ents - 1; n > 0; n = next_n) | |
408 { | |
409 next_n = 0; | |
410 for (i = 0; i < n; ++i) | |
411 if (ptr->entries[i][1] > ptr->entries[i+1][1]) | |
412 { | |
413 tmp = ptr->entries[i][0]; | |
414 ptr->entries[i][0] = ptr->entries[i+1][0]; | |
415 ptr->entries[i+1][0] = tmp; | |
416 tmp = ptr->entries[i][1]; | |
417 ptr->entries[i][1] = ptr->entries[i+1][1]; | |
418 ptr->entries[i+1][1] = tmp; | |
419 next_n = i; | |
420 } | |
421 } | |
422 return (ptr); | |
423 } | |
424 | |
425 static int | |
426 map_colortable(quant_table *qt, int num_colors) | |
427 { | |
428 register int *histp = &(qt->histogram[0][0][0]); | |
429 register C_cell *cell; | |
430 register int j, tmp, d2, dist; | |
431 int ir, ig, ib, i; | |
432 | |
433 for (ir = 0; ir < B_LEN; ++ir) | |
434 for (ig = 0; ig < B_LEN; ++ig) | |
435 for (ib = 0; ib < B_LEN; ++ib, histp++) | |
436 { | |
437 if (*histp == 0) | |
438 { | |
439 *histp = -1; | |
440 continue; | |
441 } | |
442 cell = *(qt->ColorCells + | |
443 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) + | |
444 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) + | |
445 (ib>>(B_DEPTH-C_DEPTH)))); | |
446 if (cell == NULL ) | |
447 cell = create_colorcell (qt, num_colors, | |
448 ir << COLOR_SHIFT, | |
449 ig << COLOR_SHIFT, | |
450 ib << COLOR_SHIFT); | |
451 if (cell == NULL) /* memory exhausted! punt! */ | |
452 return -1; | |
453 dist = 9999999; | |
454 for (i = 0; i < cell->num_ents && | |
455 dist > cell->entries[i][1]; ++i) | |
456 { | |
457 j = cell->entries[i][0]; | |
458 d2 = qt->rm[j] - (ir << COLOR_SHIFT); | |
459 d2 *= d2; | |
460 tmp = qt->gm[j] - (ig << COLOR_SHIFT); | |
461 d2 += tmp*tmp; | |
462 tmp = qt->bm[j] - (ib << COLOR_SHIFT); | |
463 d2 += tmp*tmp; | |
464 if (d2 < dist) | |
465 { | |
466 dist = d2; | |
467 *histp = j; | |
468 } | |
469 } | |
470 } | |
471 return 0; | |
472 } | |
473 | |
474 quant_table * | |
2367 | 475 build_EImage_quantable(Binbyte *eimage, int width, int height, int num_colors) |
428 | 476 { |
477 quant_table *qt; | |
478 Colorbox *box_list, *ptr; | |
479 int i,res; | |
480 | |
481 qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table)); | |
482 if (qt == NULL) return NULL; | |
483 | |
484 assert (num_colors < 257 && num_colors > 2); | |
485 /* | |
486 * STEP 1: create empty boxes | |
487 */ | |
488 qt->usedboxes = NULL; | |
2367 | 489 box_list = qt->freeboxes = xnew_array (Colorbox, num_colors); |
428 | 490 qt->freeboxes[0].next = &(qt->freeboxes[1]); |
491 qt->freeboxes[0].prev = NULL; | |
492 for (i = 1; i < num_colors-1; ++i) | |
493 { | |
494 qt->freeboxes[i].next = &(qt->freeboxes[i+1]); | |
495 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); | |
496 } | |
497 qt->freeboxes[num_colors-1].next = NULL; | |
498 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]); | |
499 | |
500 /* | |
501 * STEP 2: get histogram, initialize first box | |
502 */ | |
503 ptr = qt->freeboxes; | |
504 qt->freeboxes = ptr->next; | |
505 if (qt->freeboxes) | |
506 qt->freeboxes->prev = NULL; | |
507 ptr->next = qt->usedboxes; | |
508 qt->usedboxes = ptr; | |
509 if (ptr->next) | |
510 ptr->next->prev = ptr; | |
511 get_histogram (qt, eimage, width, height, ptr); | |
512 | |
513 /* | |
514 * STEP 3: continually subdivide boxes until no more free | |
515 * boxes remain or until all colors assigned. | |
516 */ | |
517 while (qt->freeboxes != NULL) | |
518 { | |
519 ptr = largest_box(qt); | |
520 if (ptr != NULL) | |
521 splitbox (qt, ptr); | |
522 else | |
523 qt->freeboxes = NULL; | |
524 } | |
525 | |
526 /* | |
527 * STEP 4: assign colors to all boxes | |
528 */ | |
529 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) | |
530 { | |
531 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; | |
532 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; | |
533 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; | |
534 qt->um[i] = ptr->total; | |
535 } | |
536 qt->num_active_colors = i; | |
537 | |
538 /* We're done with the boxes now */ | |
1726 | 539 xfree (box_list, Colorbox *); |
428 | 540 qt->freeboxes = qt->usedboxes = NULL; |
541 | |
542 /* | |
543 * STEP 5: scan histogram and map all values to closest color | |
544 */ | |
545 /* 5a: create cell list as described in Heckbert */ | |
546 qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); | |
547 /* 5b: create mapping from truncated pixel space to color | |
548 table entries */ | |
549 res = map_colortable (qt, num_colors); | |
550 | |
551 /* 5c: done with ColorCells */ | |
552 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) | |
1726 | 553 if (qt->ColorCells[i]) |
554 xfree (qt->ColorCells[i], C_cell *); | |
555 xfree (qt->ColorCells, C_cell **); | |
428 | 556 |
557 if (res) | |
558 { | |
1726 | 559 /* we failed in memory allocation, so clean up and leave */ |
560 xfree(qt, quant_table *); | |
428 | 561 return NULL; |
562 } | |
563 | |
564 return qt; | |
565 } |