Mercurial > hg > xemacs-beta
annotate src/imgproc.c @ 5353:38e24b8be4ea
Improve the lexical scoping in #'block, #'return-from.
lisp/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el:
* bytecomp.el (byte-compile-initial-macro-environment):
Shadow `block', `return-from' here, we implement them differently
when byte-compiling.
* bytecomp.el (byte-compile-active-blocks): New.
* bytecomp.el (byte-compile-block-1): New.
* bytecomp.el (byte-compile-return-from-1): New.
* bytecomp.el (return-from-1): New.
* bytecomp.el (block-1): New.
These are two aliases that exist to have their own associated
byte-compile functions, which functions implement `block' and
`return-from'.
* cl-extra.el (cl-macroexpand-all):
Fix a bug here when macros in the environment have been compiled.
* cl-macs.el (block):
* cl-macs.el (return):
* cl-macs.el (return-from):
Be more careful about lexical scope in these macros.
* cl.el:
* cl.el ('cl-block-wrapper): Removed.
* cl.el ('cl-block-throw): Removed.
These aren't needed in code generated by this XEmacs. They
shouldn't be needed in code generated by XEmacs 21.4, but if it
turns out the packages do need them, we can put them back.
2011-01-30 Mike Sperber <mike@xemacs.org>
* font-lock.el (font-lock-fontify-pending-extents): Don't fail if
`font-lock-mode' is unset, which can happen in the middle of
`revert-buffer'.
2011-01-23 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete):
* cl-macs.el (delq):
* cl-macs.el (remove):
* cl-macs.el (remq):
Don't use the compiler macro if these functions were given the
wrong number of arguments, as happens in lisp-tests.el.
* cl-seq.el (remove, remq): Removed.
I added these to subr.el, and forgot to remove them from here.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-setq, byte-compile-set):
Remove kludge allowing keywords' values to be set, all the code
that does that is gone.
* cl-compat.el (elt-satisfies-test-p):
* faces.el (set-face-parent):
* faces.el (face-doc-string):
* gtk-font-menu.el:
* gtk-font-menu.el (gtk-reset-device-font-menus):
* msw-font-menu.el:
* msw-font-menu.el (mswindows-reset-device-font-menus):
* package-get.el (package-get-installedp):
* select.el (select-convert-from-image-data):
* sound.el:
* sound.el (load-sound-file):
* x-font-menu.el (x-reset-device-font-menus-core):
Don't quote keywords, they're self-quoting, and the
win from backward-compatibility is sufficiently small now that the
style problem overrides it.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (block, return-from): Require that NAME be a symbol
in these macros, as always documented in the #'block docstring and
as required by Common Lisp.
* descr-text.el (unidata-initialize-unihan-database):
Correct the use of non-symbols in #'block and #'return-from in
this function.
2011-01-15 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (concatenate): Accept more complicated TYPEs in this
function, handing the sequences over to #'coerce if we don't
understand them here.
* cl-macs.el (inline): Don't proclaim #'concatenate as inline, its
compiler macro is more useful than doing that.
2011-01-11 Aidan Kehoe <kehoea@parhasard.net>
* subr.el (delete, delq, remove, remq): Move #'remove, #'remq
here, they don't belong in cl-seq.el; move #'delete, #'delq here
from fns.c, implement them in terms of #'delete*, allowing support
for sequences generally.
* update-elc.el (do-autoload-commands): Use #'delete*, not #'delq
here, now the latter's no longer dumped.
* cl-macs.el (delete, delq): Add compiler macros transforming
#'delete and #'delq to #'delete* calls.
2011-01-10 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box): Correct a misplaced parenthesis
here, thank you Mats Lidell in 87zkr9gqrh.fsf@mail.contactor.se !
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box):
* list-mode.el (display-completion-list):
These functions used to use cl-parsing-keywords; change them to
use defun* instead, fixing the build. (Not sure what led to me
not including this change in d1b17a33450b!)
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (define-star-compiler-macros):
Make sure the form has ITEM and LIST specified before attempting
to change to calls with explicit tests; necessary for some tests
in lisp-tests.el to compile correctly.
(stable-union, stable-intersection): Add compiler macros for these
functions, in the same way we do for most of the other functions
in cl-seq.el.
2011-01-01 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (dolist, dotimes, do-symbols, macrolet)
(symbol-macrolet):
Define these macros with defmacro* instead of parsing the argument
list by hand, for the sake of style and readability; use backquote
where appropriate, instead of calling #'list and and friends, for
the same reason.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* x-misc.el (device-x-display):
Provide this function, documented in the Lispref for years, but
not existing previously. Thank you Julian Bradfield, thank you
Jeff Mincy.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl-seq.el:
Move the heavy lifting from this file to C. Dump the
cl-parsing-keywords macro, but don't use defun* for the functions
we define that do take keywords, dynamic scope lossage makes that
not practical.
* subr.el (sort, fillarray): Move these aliases here.
(map-plist): #'nsublis is now built-in, but at this point #'eql
isn't necessarily available as a test; use #'eq.
* obsolete.el (cl-delete-duplicates): Make this available for old
compiler macros and old code.
(memql): Document that this is equivalent to #'member*, and worse.
* cl.el (adjoin, subst): Removed. These are in C.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* simple.el (assoc-ignore-case): Remove a duplicate definition of
this function (it's already in subr.el).
* iso8859-1.el (char-width):
On non-Mule, make this function equivalent to that produced by
(constantly 1), but preserve its docstring.
* subr.el (subst-char-in-string): Define this in terms of
#'substitute, #'nsubstitute.
(string-width): Define this using #'reduce and #'char-width.
(char-width): Give this a simpler definition, it makes far more
sense to check for mule at load time and redefine, as we do in
iso8859-1.el.
(store-substring): Implement this in terms of #'replace, now
#'replace is cheap.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* update-elc.el (lisp-files-needed-for-byte-compilation)
(lisp-files-needing-early-byte-compilation):
cl-macs belongs in the former, not the latter, it is as
fundamental as bytecomp.el.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl.el:
Provde the Common Lisp program-error, type-error as error
symbols. This doesn't nearly go far enough for anyone using the
Common Lisp errors.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete-duplicates):
If the form has an incorrect number of arguments, don't attempt a
compiler macroexpansion.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (cl-safe-expr-p):
Forms that start with the symbol lambda are also safe.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
For these functions' compiler macros, the optimisation is safe
even if the first and the last arguments have side effects, since
they're only used the once.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (inline-side-effect-free-compiler-macros):
Unroll a loop here at macro-expansion time, so these compiler
macros are compiled. Use #'eql instead of #'eq in a couple of
places for better style.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (notany, notevery): Avoid some dynamic scope
stupidity with local variable names in these functions, when they
weren't prefixed with cl-; go into some more detail in the doc
strings.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns): #'remove, #'remq are
free of side-effects.
(side-effect-and-error-free-fns):
Drop dot, dot-marker from the list.
2010-11-17 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (coerce):
In the argument list, name the first argument OBJECT, not X; the
former name was always used in the doc string and is clearer.
Handle vector type specifications which include the length of the
target sequence, error if there's a mismatch.
* cl-macs.el (cl-make-type-test): Handle type specifications
starting with the symbol 'eql.
2010-11-14 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (eql): Don't remove the byte-compile property of this
symbol. That was necessary to override a bug in bytecomp.el where
#'eql was confused with #'eq, which bug we no longer have.
If neither expression is constant, don't attempt to handle the
expression in this compiler macro, leave it to byte-compile-eql,
which produces better code anyway.
* bytecomp.el (eq): #'eql is not the function associated with the
byte-eq byte code.
(byte-compile-eql): Add an explicit compile method for this
function, for cases where the cl-macs compiler macro hasn't
reduced it to #'eq or #'equal.
2010-10-25 Aidan Kehoe <kehoea@parhasard.net>
Add compiler macros and compilation sanity-checking for various
functions that take keywords.
* byte-optimize.el (side-effect-free-fns): #'symbol-value is
side-effect free and not error free.
* bytecomp.el (byte-compile-normal-call): Check keyword argument
lists for sanity; store information about the positions where
keyword arguments start using the new byte-compile-keyword-start
property.
* cl-macs.el (cl-const-expr-val): Take a new optional argument,
cl-not-constant, defaulting to nil, in this function; return it if
the expression is not constant.
(cl-non-fixnum-number-p): Make this into a separate function, we
want to pass it to #'every.
(eql): Use it.
(define-star-compiler-macros): Use the same code to generate the
member*, assoc* and rassoc* compiler macros; special-case some
code in #'add-to-list in subr.el.
(remove, remq): Add compiler macros for these two functions, in
preparation for #'remove being in C.
(define-foo-if-compiler-macros): Transform (remove-if-not ...) calls to
(remove ... :if-not) at compile time, which will be a real win
once the latter is in C.
(define-substitute-if-compiler-macros)
(define-subst-if-compiler-macros): Similarly for these functions.
(delete-duplicates): Change this compiler macro to use
#'plists-equal; if we don't have information about the type of
SEQUENCE at compile time, don't bother attempting to inline the
call, the function will be in C soon enough.
(equalp): Remove an old commented-out compiler macro for this, if
we want to see it it's in version control.
(subst-char-in-string): Transform this to a call to nsubstitute or
nsubstitute, if that is appropriate.
* cl.el (ldiff): Don't call setf here, this makes for a load-time
dependency problem in cl-macs.el
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* term/vt100.el:
Refer to XEmacs, not GNU Emacs, in permissions.
* term/bg-mouse.el:
* term/sup-mouse.el:
Put copyright notice in canonical "Copyright DATE AUTHOR" form.
Refer to XEmacs, not GNU Emacs, in permissions.
* site-load.el:
Add permission boilerplate.
* mule/canna-leim.el:
* alist.el:
Refer to XEmacs, not APEL/this program, in permissions.
* mule/canna-leim.el:
Remove my copyright, I've assigned it to the FSF.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* gtk.el:
* gtk-widget-accessors.el:
* gtk-package.el:
* gtk-marshal.el:
* gtk-compose.el:
* gnome.el:
Add copyright notice based on internal evidence.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* easymenu.el: Add reference to COPYING to permission notice.
* gutter.el:
* gutter-items.el:
* menubar-items.el:
Fix typo "Xmacs" in permissions notice.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* auto-save.el:
* font.el:
* fontconfig.el:
* mule/kinsoku.el:
Add "part of XEmacs" text to permission notice.
2010-10-14 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns):
* cl-macs.el (remf, getf):
* cl-extra.el (tailp, cl-set-getf, cl-do-remf):
* cl.el (ldiff, endp):
Tighten up Common Lisp compatibility for #'ldiff, #'endp, #'tailp;
add circularity checking for the first two.
#'cl-set-getf and #'cl-do-remf were Lisp implementations of
#'plist-put and #'plist-remprop; change the names to aliases,
changes the macros that use them to using #'plist-put and
#'plist-remprop directly.
2010-10-12 Aidan Kehoe <kehoea@parhasard.net>
* abbrev.el (fundamental-mode-abbrev-table, global-abbrev-table):
Create both these abbrev tables using the usual
#'define-abbrev-table calls, rather than attempting to
special-case them.
* cl-extra.el: Force cl-macs to be loaded here, if cl-extra.el is
being loaded interpreted. Previously other, later files would
redundantly call (load "cl-macs") when interpreted, it's more
reasonable to do it here, once.
* cmdloop.el (read-quoted-char-radix): Use defcustom here, we
don't have any dump-order dependencies that would prevent that.
* custom.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling, rely on cl-extra.el in the
former case and the appropriate entry in bytecomp-load-hook in the
latter. Get rid of custom-declare-variable-list, we have no
dump-time dependencies that would require it.
* faces.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling.
* packages.el: Remove some inaccurate comments.
* post-gc.el (cleanup-simple-finalizers): Use #'delete-if-not
here, now the order of preloaded-file-list has been changed to
make it available.
* subr.el (custom-declare-variable-list): Remove. No need for it.
Also remove a stub define-abbrev-table from this file, given the
current order of preloaded-file-list there's no need for it.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-constp) Forms quoted with FUNCTION are
also constant.
(byte-compile-initial-macro-environment): In #'the, if FORM is
constant and does not match TYPE, warn at byte-compile time.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* backquote.el (bq-vector-contents, bq-list*): Remove; the former
is equivalent to (append VECTOR nil), the latter to (list* ...).
(bq-process-2): Use (append VECTOR nil) instead of using
#'bq-vector-contents to convert to a list.
(bq-process-1): Now we use list* instead of bq-list
* subr.el (list*): Moved from cl.el, since it is now required to
be available the first time a backquoted form is encountered.
* cl.el (list*): Move to subr.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* test-harness.el (Check-Message):
Add an omitted comma here, thank you the buildbot.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* hash-table.el (hash-table-key-list, hash-table-value-list)
(hash-table-key-value-alist, hash-table-key-value-plist):
Remove some useless #'nreverse calls in these files; our hash
tables have no order, it's not helpful to pretend they do.
* behavior.el (read-behavior):
Do the same in this file, in some code evidently copied from
hash-table.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* info.el (Info-insert-dir):
* format.el (format-deannotate-region):
* files.el (cd, save-buffers-kill-emacs):
Use #'some, #'every and related functions for applying boolean
operations to lists, instead of rolling our own ones that cons and
don't short-circuit.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-initial-macro-environment):
* cl-macs.el (the):
Rephrase the docstring, make its implementation when compiling
files a little nicer.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* descr-text.el (unidata-initialize-unicodedata-database)
(unidata-initialize-unihan-database, describe-char-unicode-data)
(describe-char-unicode-data):
Wrap calls to the database functions with (with-fboundp ...),
avoiding byte compile warnings on builds without support for the
database functions.
(describe-char): (reduce #'max ...), not (apply #'max ...), no
need to cons needlessly.
(describe-char): Remove a redundant lambda wrapping
#'extent-properties.
(describe-char-unicode-data): Call #'nsubst when replacing "" with
nil in the result of #'split-string, instead of consing inside
mapcar.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* x-faces.el (x-available-font-sizes):
* specifier.el (let-specifier):
* package-ui.el (pui-add-required-packages):
* msw-faces.el (mswindows-available-font-sizes):
* modeline.el (modeline-minor-mode-menu):
* minibuf.el (minibuf-directory-files):
Replace the O2N (delq nil (mapcar (lambda (W) (and X Y)) Z)) with
the ON (mapcan (lambda (W) (and X (list Y))) Z) in these files.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
When these functions are handed more than two arguments, and those
arguments have no side effects, transform to a series of two
argument calls, avoiding funcall in the byte-compiled code.
* mule/mule-cmds.el (finish-set-language-environment):
Take advantage of this change in a function called 256 times at
startup.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-function-form, byte-compile-quote)
(byte-compile-quote-form):
Warn at compile time, and error at runtime, if a (quote ...) or a
(function ...) form attempts to quote more than one object.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (byte-optimize-apply): Transform (apply 'nconc
(mapcar ...)) to (mapcan ...); warn about use of the first idiom.
* update-elc.el (do-autoload-commands):
* packages.el (packages-find-package-library-path):
* frame.el (frame-list):
* extents.el (extent-descendants):
* etags.el (buffer-tag-table-files):
* dumped-lisp.el (preloaded-file-list):
* device.el (device-list):
* bytecomp-runtime.el (proclaim-inline, proclaim-notinline)
Use #'mapcan, not (apply #'nconc (mapcar ...) in all these files.
* bytecomp-runtime.el (eval-when-compile, eval-and-compile):
In passing, mention that these macros also evaluate the body when
interpreted.
tests/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* automated/lisp-tests.el:
Test lexical scope for `block', `return-from'; add a
Known-Bug-Expect-Failure for a contorted example that fails when
byte-compiled.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Mon, 07 Feb 2011 12:01:24 +0000 |
| parents | 6c6d78781d59 |
| children | 2aa9cd456ae7 |
| 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. | |
|
5169
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
30 Copyright (C) 2010 Ben Wing. |
| 428 | 31 |
| 32 Permission to use, copy, modify, distribute, and sell this software and | |
| 33 its documentation for any purpose is hereby granted without fee, provided | |
| 34 that (i) the above copyright notices and this permission notice appear in | |
| 35 all copies of the software and related documentation, and (ii) the names of | |
| 36 Sam Leffler and Silicon Graphics may not be used in any advertising or | |
| 37 publicity relating to the software without the specific, prior written | |
| 38 permission of Sam Leffler and Silicon Graphics. */ | |
| 39 | |
| 40 /* Quantizing code based off of the paper | |
| 41 Color Image Quantization for Frame Buffer Display, Paul Heckbert, | |
| 42 Siggraph '82 proceedings, pp. 297-307 */ | |
| 43 | |
| 44 #include <config.h> | |
| 45 #include "lisp.h" | |
| 46 #include "imgproc.h" | |
| 47 | |
| 48 static void | |
| 2367 | 49 get_histogram(quant_table *qt, Binbyte *pic, |
| 428 | 50 int width, int height, Colorbox* box) |
| 51 { | |
| 2367 | 52 register Binbyte *inptr; |
| 428 | 53 register int red, green, blue; |
| 647 | 54 register int j, i; |
| 428 | 55 |
| 56 box->rmin = box->gmin = box->bmin = 999; | |
| 57 box->rmax = box->gmax = box->bmax = -1; | |
| 58 box->total = width * height; | |
| 59 | |
| 60 inptr = pic; | |
| 61 for (i = 0; i < height; i++) | |
| 62 { | |
| 63 for (j = width; j-- > 0;) | |
| 64 { | |
| 65 red = *inptr++ >> COLOR_SHIFT; | |
| 66 green = *inptr++ >> COLOR_SHIFT; | |
| 67 blue = *inptr++ >> COLOR_SHIFT; | |
| 68 if (red < box->rmin) | |
| 69 box->rmin = red; | |
| 70 if (red > box->rmax) | |
| 71 box->rmax = red; | |
| 72 if (green < box->gmin) | |
| 73 box->gmin = green; | |
| 74 if (green > box->gmax) | |
| 75 box->gmax = green; | |
| 76 if (blue < box->bmin) | |
| 77 box->bmin = blue; | |
| 78 if (blue > box->bmax) | |
| 79 box->bmax = blue; | |
| 80 qt->histogram[red][green][blue]++; | |
| 81 } | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 static Colorbox * | |
| 86 largest_box(quant_table *qt) | |
| 87 { | |
| 88 register Colorbox *p, *b; | |
| 89 register int size; | |
| 90 | |
| 91 b = NULL; | |
| 92 size = -1; | |
| 93 for (p = qt->usedboxes; p != NULL; p = p->next) | |
| 94 if ((p->rmax > p->rmin || p->gmax > p->gmin || | |
| 95 p->bmax > p->bmin) && p->total > size) | |
| 96 size = (b = p)->total; | |
| 97 return (b); | |
| 98 } | |
| 99 | |
| 100 static void | |
| 101 shrinkbox(quant_table *qt, Colorbox* box) | |
| 102 { | |
| 103 register int *histp, ir, ig, ib; | |
| 104 | |
| 105 if (box->rmax > box->rmin) | |
| 106 { | |
| 107 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
| 108 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
| 109 { | |
| 110 histp = &(qt->histogram[ir][ig][box->bmin]); | |
| 111 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
| 112 if (*histp++ != 0) | |
| 113 { | |
| 114 box->rmin = ir; | |
| 115 goto have_rmin; | |
| 116 } | |
| 117 } | |
| 118 have_rmin: | |
| 119 if (box->rmax > box->rmin) | |
| 120 for (ir = box->rmax; ir >= box->rmin; --ir) | |
| 121 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
| 122 { | |
| 123 histp = &(qt->histogram[ir][ig][box->bmin]); | |
| 124 ib = box->bmin; | |
| 125 for (; ib <= box->bmax; ++ib) | |
| 126 if (*histp++ != 0) | |
| 127 { | |
| 128 box->rmax = ir; | |
| 129 goto have_rmax; | |
| 130 } | |
| 131 } | |
| 132 } | |
| 133 have_rmax: | |
| 134 if (box->gmax > box->gmin) | |
| 135 { | |
| 136 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
| 137 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
| 138 { | |
| 139 histp = &(qt->histogram[ir][ig][box->bmin]); | |
| 140 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
| 141 if (*histp++ != 0) | |
| 142 { | |
| 143 box->gmin = ig; | |
| 144 goto have_gmin; | |
| 145 } | |
| 146 } | |
| 147 have_gmin: | |
| 148 if (box->gmax > box->gmin) | |
| 149 for (ig = box->gmax; ig >= box->gmin; --ig) | |
| 150 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
| 151 { | |
| 152 histp = &(qt->histogram[ir][ig][box->bmin]); | |
| 153 ib = box->bmin; | |
| 154 for (; ib <= box->bmax; ++ib) | |
| 155 if (*histp++ != 0) | |
| 156 { | |
| 157 box->gmax = ig; | |
| 158 goto have_gmax; | |
| 159 } | |
| 160 } | |
| 161 } | |
| 162 have_gmax: | |
| 163 if (box->bmax > box->bmin) | |
| 164 { | |
| 165 for (ib = box->bmin; ib <= box->bmax; ++ib) | |
| 166 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
| 167 { | |
| 168 histp = &(qt->histogram[ir][box->gmin][ib]); | |
| 169 for (ig = box->gmin; ig <= box->gmax; ++ig) | |
| 170 { | |
| 171 if (*histp != 0) | |
| 172 { | |
| 173 box->bmin = ib; | |
| 174 goto have_bmin; | |
| 175 } | |
| 176 histp += B_LEN; | |
| 177 } | |
| 178 } | |
| 179 have_bmin: | |
| 180 if (box->bmax > box->bmin) | |
| 181 for (ib = box->bmax; ib >= box->bmin; --ib) | |
| 182 for (ir = box->rmin; ir <= box->rmax; ++ir) | |
| 183 { | |
| 184 histp = &(qt->histogram[ir][box->gmin][ib]); | |
| 185 ig = box->gmin; | |
| 186 for (; ig <= box->gmax; ++ig) | |
| 187 { | |
| 188 if (*histp != 0) | |
| 189 { | |
| 190 box->bmax = ib; | |
| 191 goto have_bmax; | |
| 192 } | |
| 193 histp += B_LEN; | |
| 194 } | |
| 195 } | |
| 196 } | |
| 197 have_bmax: | |
| 198 ; | |
| 199 } | |
| 200 | |
| 201 static void | |
| 202 splitbox(quant_table *qt, Colorbox* ptr) | |
| 203 { | |
| 204 int hist2[B_LEN]; | |
| 205 int first = 0, last = 0; | |
| 3025 | 206 register Colorbox *new_; |
| 428 | 207 register int *iptr, *histp; |
| 208 register int i, j; | |
| 209 register int ir,ig,ib; | |
| 210 register int sum, sum1, sum2; | |
| 211 enum { RED, GREEN, BLUE } axis; | |
| 212 | |
| 213 /* | |
| 214 * See which axis is the largest, do a histogram along that | |
| 215 * axis. Split at median point. Contract both new boxes to | |
| 216 * fit points and return | |
| 217 */ | |
| 218 i = ptr->rmax - ptr->rmin; | |
| 219 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin) | |
| 220 axis = RED; | |
| 221 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin) | |
| 222 axis = GREEN; | |
| 223 else | |
| 224 axis = BLUE; | |
| 225 /* get histogram along longest axis */ | |
| 226 switch (axis) | |
| 227 { | |
| 228 case RED: | |
| 229 histp = &hist2[ptr->rmin]; | |
| 230 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
| 231 { | |
| 232 *histp = 0; | |
| 233 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
| 234 { | |
| 235 iptr = &(qt->histogram[ir][ig][ptr->bmin]); | |
| 236 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
| 237 *histp += *iptr++; | |
| 238 } | |
| 239 histp++; | |
| 240 } | |
| 241 first = ptr->rmin; | |
| 242 last = ptr->rmax; | |
| 243 break; | |
| 244 case GREEN: | |
| 245 histp = &hist2[ptr->gmin]; | |
| 246 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
| 247 { | |
| 248 *histp = 0; | |
| 249 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
| 250 { | |
| 251 iptr = &(qt->histogram[ir][ig][ptr->bmin]); | |
| 252 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
| 253 *histp += *iptr++; | |
| 254 } | |
| 255 histp++; | |
| 256 } | |
| 257 first = ptr->gmin; | |
| 258 last = ptr->gmax; | |
| 259 break; | |
| 260 case BLUE: | |
| 261 histp = &hist2[ptr->bmin]; | |
| 262 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) | |
| 263 { | |
| 264 *histp = 0; | |
| 265 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) | |
| 266 { | |
| 267 iptr = &(qt->histogram[ir][ptr->gmin][ib]); | |
| 268 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) | |
| 269 { | |
| 270 *histp += *iptr; | |
| 271 iptr += B_LEN; | |
| 272 } | |
| 273 } | |
| 274 histp++; | |
| 275 } | |
| 276 first = ptr->bmin; | |
| 277 last = ptr->bmax; | |
| 278 break; | |
| 279 } | |
| 280 /* find median point */ | |
| 281 sum2 = ptr->total / 2; | |
| 282 histp = &hist2[first]; | |
| 283 sum = 0; | |
| 284 for (i = first; i <= last && (sum += *histp++) < sum2; ++i) | |
| 285 ; | |
| 286 if (i == first) | |
| 287 i++; | |
| 288 | |
| 289 /* Create new box, re-allocate points */ | |
| 3025 | 290 new_ = qt->freeboxes; |
| 291 qt->freeboxes = new_->next; | |
| 428 | 292 if (qt->freeboxes) |
| 293 qt->freeboxes->prev = NULL; | |
| 294 if (qt->usedboxes) | |
| 3025 | 295 qt->usedboxes->prev = new_; |
| 296 new_->next = qt->usedboxes; | |
| 297 qt->usedboxes = new_; | |
| 428 | 298 |
| 299 histp = &hist2[first]; | |
| 300 for (sum1 = 0, j = first; j < i; j++) | |
| 301 sum1 += *histp++; | |
| 302 for (sum2 = 0, j = i; j <= last; j++) | |
| 303 sum2 += *histp++; | |
| 3025 | 304 new_->total = sum1; |
| 428 | 305 ptr->total = sum2; |
| 306 | |
| 3025 | 307 new_->rmin = ptr->rmin; |
| 308 new_->rmax = ptr->rmax; | |
| 309 new_->gmin = ptr->gmin; | |
| 310 new_->gmax = ptr->gmax; | |
| 311 new_->bmin = ptr->bmin; | |
| 312 new_->bmax = ptr->bmax; | |
| 428 | 313 switch (axis) |
| 314 { | |
| 315 case RED: | |
| 3025 | 316 new_->rmax = i-1; |
| 428 | 317 ptr->rmin = i; |
| 318 break; | |
| 319 case GREEN: | |
| 3025 | 320 new_->gmax = i-1; |
| 428 | 321 ptr->gmin = i; |
| 322 break; | |
| 323 case BLUE: | |
| 3025 | 324 new_->bmax = i-1; |
| 428 | 325 ptr->bmin = i; |
| 326 break; | |
| 327 } | |
| 3025 | 328 shrinkbox (qt, new_); |
| 428 | 329 shrinkbox (qt, ptr); |
| 330 } | |
| 331 | |
| 332 | |
| 333 static C_cell * | |
| 334 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue) | |
| 335 { | |
| 336 register int ir, ig, ib, i; | |
| 337 register C_cell *ptr; | |
| 338 int mindist, next_n; | |
| 339 register int tmp, dist, n; | |
| 340 | |
| 341 ir = red >> (COLOR_DEPTH-C_DEPTH); | |
| 342 ig = green >> (COLOR_DEPTH-C_DEPTH); | |
| 343 ib = blue >> (COLOR_DEPTH-C_DEPTH); | |
| 2367 | 344 ptr = xnew (C_cell); |
| 428 | 345 *(qt->ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr; |
| 346 ptr->num_ents = 0; | |
| 347 | |
| 348 /* | |
| 349 * Step 1: find all colors inside this cell, while we're at | |
| 350 * it, find distance of centermost point to furthest corner | |
| 351 */ | |
| 352 mindist = 99999999; | |
| 353 for (i = 0; i < num_colors; ++i) | |
| 354 { | |
| 355 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || | |
| 356 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || | |
| 357 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) | |
| 358 continue; | |
| 359 ptr->entries[ptr->num_ents][0] = i; | |
| 360 ptr->entries[ptr->num_ents][1] = 0; | |
| 361 ++ptr->num_ents; | |
| 362 tmp = qt->rm[i] - red; | |
| 363 if (tmp < (MAX_COLOR/C_LEN/2)) | |
| 364 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
| 365 dist = tmp*tmp; | |
| 366 tmp = qt->gm[i] - green; | |
| 367 if (tmp < (MAX_COLOR/C_LEN/2)) | |
| 368 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
| 369 dist += tmp*tmp; | |
| 370 tmp = qt->bm[i] - blue; | |
| 371 if (tmp < (MAX_COLOR/C_LEN/2)) | |
| 372 tmp = MAX_COLOR/C_LEN-1 - tmp; | |
| 373 dist += tmp*tmp; | |
| 374 if (dist < mindist) | |
| 375 mindist = dist; | |
| 376 } | |
| 377 | |
| 378 /* | |
| 379 * Step 3: find all points within that distance to cell. | |
| 380 */ | |
| 381 for (i = 0; i < num_colors; ++i) | |
| 382 { | |
| 383 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && | |
| 384 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && | |
| 385 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) | |
| 386 continue; | |
| 387 dist = 0; | |
| 388 if ((tmp = red - qt->rm[i]) > 0 || | |
| 389 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) | |
| 390 dist += tmp*tmp; | |
| 391 if ((tmp = green - qt->gm[i]) > 0 || | |
| 392 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) | |
| 393 dist += tmp*tmp; | |
| 394 if ((tmp = blue - qt->bm[i]) > 0 || | |
| 395 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 ) | |
| 396 dist += tmp*tmp; | |
| 397 if (dist < mindist) | |
| 398 { | |
| 399 ptr->entries[ptr->num_ents][0] = i; | |
| 400 ptr->entries[ptr->num_ents][1] = dist; | |
| 401 ++ptr->num_ents; | |
| 402 } | |
| 403 } | |
| 404 | |
| 405 /* | |
| 406 * Sort color cells by distance, use cheap exchange sort | |
| 407 */ | |
| 408 for (n = ptr->num_ents - 1; n > 0; n = next_n) | |
| 409 { | |
| 410 next_n = 0; | |
| 411 for (i = 0; i < n; ++i) | |
| 412 if (ptr->entries[i][1] > ptr->entries[i+1][1]) | |
| 413 { | |
| 414 tmp = ptr->entries[i][0]; | |
| 415 ptr->entries[i][0] = ptr->entries[i+1][0]; | |
| 416 ptr->entries[i+1][0] = tmp; | |
| 417 tmp = ptr->entries[i][1]; | |
| 418 ptr->entries[i][1] = ptr->entries[i+1][1]; | |
| 419 ptr->entries[i+1][1] = tmp; | |
| 420 next_n = i; | |
| 421 } | |
| 422 } | |
| 423 return (ptr); | |
| 424 } | |
| 425 | |
| 426 static int | |
| 427 map_colortable(quant_table *qt, int num_colors) | |
| 428 { | |
| 429 register int *histp = &(qt->histogram[0][0][0]); | |
| 430 register C_cell *cell; | |
| 431 register int j, tmp, d2, dist; | |
| 432 int ir, ig, ib, i; | |
| 433 | |
| 434 for (ir = 0; ir < B_LEN; ++ir) | |
| 435 for (ig = 0; ig < B_LEN; ++ig) | |
| 436 for (ib = 0; ib < B_LEN; ++ib, histp++) | |
| 437 { | |
| 438 if (*histp == 0) | |
| 439 { | |
| 440 *histp = -1; | |
| 441 continue; | |
| 442 } | |
| 443 cell = *(qt->ColorCells + | |
| 444 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) + | |
| 445 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) + | |
| 446 (ib>>(B_DEPTH-C_DEPTH)))); | |
| 447 if (cell == NULL ) | |
| 448 cell = create_colorcell (qt, num_colors, | |
| 449 ir << COLOR_SHIFT, | |
| 450 ig << COLOR_SHIFT, | |
| 451 ib << COLOR_SHIFT); | |
| 452 if (cell == NULL) /* memory exhausted! punt! */ | |
| 453 return -1; | |
| 454 dist = 9999999; | |
| 455 for (i = 0; i < cell->num_ents && | |
| 456 dist > cell->entries[i][1]; ++i) | |
| 457 { | |
| 458 j = cell->entries[i][0]; | |
| 459 d2 = qt->rm[j] - (ir << COLOR_SHIFT); | |
| 460 d2 *= d2; | |
| 461 tmp = qt->gm[j] - (ig << COLOR_SHIFT); | |
| 462 d2 += tmp*tmp; | |
| 463 tmp = qt->bm[j] - (ib << COLOR_SHIFT); | |
| 464 d2 += tmp*tmp; | |
| 465 if (d2 < dist) | |
| 466 { | |
| 467 dist = d2; | |
| 468 *histp = j; | |
| 469 } | |
| 470 } | |
| 471 } | |
| 472 return 0; | |
| 473 } | |
| 474 | |
| 475 quant_table * | |
| 2367 | 476 build_EImage_quantable(Binbyte *eimage, int width, int height, int num_colors) |
| 428 | 477 { |
| 478 quant_table *qt; | |
| 479 Colorbox *box_list, *ptr; | |
| 480 int i,res; | |
| 481 | |
| 482 qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table)); | |
| 483 if (qt == NULL) return NULL; | |
| 484 | |
| 485 assert (num_colors < 257 && num_colors > 2); | |
| 486 /* | |
| 487 * STEP 1: create empty boxes | |
| 488 */ | |
| 489 qt->usedboxes = NULL; | |
| 2367 | 490 box_list = qt->freeboxes = xnew_array (Colorbox, num_colors); |
| 428 | 491 qt->freeboxes[0].next = &(qt->freeboxes[1]); |
| 492 qt->freeboxes[0].prev = NULL; | |
| 493 for (i = 1; i < num_colors-1; ++i) | |
| 494 { | |
| 495 qt->freeboxes[i].next = &(qt->freeboxes[i+1]); | |
| 496 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); | |
| 497 } | |
| 498 qt->freeboxes[num_colors-1].next = NULL; | |
| 499 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]); | |
| 500 | |
| 501 /* | |
| 502 * STEP 2: get histogram, initialize first box | |
| 503 */ | |
| 504 ptr = qt->freeboxes; | |
| 505 qt->freeboxes = ptr->next; | |
| 506 if (qt->freeboxes) | |
| 507 qt->freeboxes->prev = NULL; | |
| 508 ptr->next = qt->usedboxes; | |
| 509 qt->usedboxes = ptr; | |
| 510 if (ptr->next) | |
| 511 ptr->next->prev = ptr; | |
| 512 get_histogram (qt, eimage, width, height, ptr); | |
| 513 | |
| 514 /* | |
| 515 * STEP 3: continually subdivide boxes until no more free | |
| 516 * boxes remain or until all colors assigned. | |
| 517 */ | |
| 518 while (qt->freeboxes != NULL) | |
| 519 { | |
| 520 ptr = largest_box(qt); | |
| 521 if (ptr != NULL) | |
| 522 splitbox (qt, ptr); | |
| 523 else | |
| 524 qt->freeboxes = NULL; | |
| 525 } | |
| 526 | |
| 527 /* | |
| 528 * STEP 4: assign colors to all boxes | |
| 529 */ | |
| 530 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) | |
| 531 { | |
| 532 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; | |
| 533 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; | |
| 534 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; | |
| 535 qt->um[i] = ptr->total; | |
| 536 } | |
| 537 qt->num_active_colors = i; | |
| 538 | |
| 539 /* We're done with the boxes now */ | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
540 xfree (box_list); |
| 428 | 541 qt->freeboxes = qt->usedboxes = NULL; |
| 542 | |
| 543 /* | |
| 544 * STEP 5: scan histogram and map all values to closest color | |
| 545 */ | |
| 546 /* 5a: create cell list as described in Heckbert */ | |
| 547 qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); | |
| 548 /* 5b: create mapping from truncated pixel space to color | |
| 549 table entries */ | |
| 550 res = map_colortable (qt, num_colors); | |
| 551 | |
| 552 /* 5c: done with ColorCells */ | |
| 553 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) | |
| 1726 | 554 if (qt->ColorCells[i]) |
|
5169
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
555 { |
|
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
556 xfree (qt->ColorCells[i]); |
|
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
557 qt->ColorCells[i] = 0; |
|
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
558 } |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
559 xfree (qt->ColorCells); |
|
5169
6c6d78781d59
cleanup of code related to xfree(), better KKCC backtrace capabilities, document XD_INLINE_LISP_OBJECT_BLOCK_PTR, fix some memory leaks, other code cleanup
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
560 qt->ColorCells = 0; |
| 428 | 561 |
| 562 if (res) | |
| 563 { | |
| 1726 | 564 /* we failed in memory allocation, so clean up and leave */ |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
565 xfree (qt); |
| 428 | 566 return NULL; |
| 567 } | |
| 568 | |
| 569 return qt; | |
| 570 } |