Mercurial > hg > xemacs-beta
view src/imgproc.c @ 4952:19a72041c5ed
Mule-izing, various fixes related to char * arguments
-------------------- ChangeLog entries follow: --------------------
modules/ChangeLog addition:
2010-01-26 Ben Wing <ben@xemacs.org>
* postgresql/postgresql.c:
* postgresql/postgresql.c (CHECK_LIVE_CONNECTION):
* postgresql/postgresql.c (print_pgresult):
* postgresql/postgresql.c (Fpq_conn_defaults):
* postgresql/postgresql.c (Fpq_connectdb):
* postgresql/postgresql.c (Fpq_connect_start):
* postgresql/postgresql.c (Fpq_result_status):
* postgresql/postgresql.c (Fpq_res_status):
Mule-ize large parts of it.
2010-01-26 Ben Wing <ben@xemacs.org>
* ldap/eldap.c (print_ldap):
* ldap/eldap.c (allocate_ldap):
Use write_ascstring().
src/ChangeLog addition:
2010-01-26 Ben Wing <ben@xemacs.org>
* alloc.c:
* alloc.c (build_ascstring):
* alloc.c (build_msg_cistring):
* alloc.c (staticpro_1):
* alloc.c (staticpro_name):
* alloc.c (staticpro_nodump_1):
* alloc.c (staticpro_nodump_name):
* alloc.c (unstaticpro_nodump_1):
* alloc.c (mcpro_1):
* alloc.c (mcpro_name):
* alloc.c (object_memory_usage_stats):
* alloc.c (common_init_alloc_early):
* alloc.c (init_alloc_once_early):
* buffer.c (print_buffer):
* buffer.c (vars_of_buffer):
* buffer.c (common_init_complex_vars_of_buffer):
* buffer.c (init_initial_directory):
* bytecode.c (invalid_byte_code):
* bytecode.c (print_compiled_function):
* bytecode.c (mark_compiled_function):
* chartab.c (print_table_entry):
* chartab.c (print_char_table):
* config.h.in:
* console-gtk.c:
* console-gtk.c (gtk_device_to_console_connection):
* console-gtk.c (gtk_semi_canonicalize_console_connection):
* console-gtk.c (gtk_canonicalize_console_connection):
* console-gtk.c (gtk_semi_canonicalize_device_connection):
* console-gtk.c (gtk_canonicalize_device_connection):
* console-stream.c (stream_init_frame_1):
* console-stream.c (vars_of_console_stream):
* console-stream.c (init_console_stream):
* console-x.c (x_semi_canonicalize_console_connection):
* console-x.c (x_semi_canonicalize_device_connection):
* console-x.c (x_canonicalize_device_connection):
* console-x.h:
* data.c (eq_with_ebola_notice):
* data.c (Fsubr_interactive):
* data.c (Fnumber_to_string):
* data.c (digit_to_number):
* device-gtk.c (gtk_init_device):
* device-msw.c (print_devmode):
* device-x.c (x_event_name):
* dialog-msw.c (handle_directory_dialog_box):
* dialog-msw.c (handle_file_dialog_box):
* dialog-msw.c (vars_of_dialog_mswindows):
* doc.c (weird_doc):
* doc.c (Fsnarf_documentation):
* doc.c (vars_of_doc):
* dumper.c (pdump):
* dynarr.c:
* dynarr.c (Dynarr_realloc):
* editfns.c (Fuser_real_login_name):
* editfns.c (get_home_directory):
* elhash.c (print_hash_table_data):
* elhash.c (print_hash_table):
* emacs.c (main_1):
* emacs.c (vars_of_emacs):
* emodules.c:
* emodules.c (_emodules_list):
* emodules.c (Fload_module):
* emodules.c (Funload_module):
* emodules.c (Flist_modules):
* emodules.c (find_make_module):
* emodules.c (attempt_module_delete):
* emodules.c (emodules_load):
* emodules.c (emodules_doc_subr):
* emodules.c (emodules_doc_sym):
* emodules.c (syms_of_module):
* emodules.c (vars_of_module):
* emodules.h:
* eval.c (print_subr):
* eval.c (signal_call_debugger):
* eval.c (build_error_data):
* eval.c (signal_error):
* eval.c (maybe_signal_error):
* eval.c (signal_continuable_error):
* eval.c (maybe_signal_continuable_error):
* eval.c (signal_error_2):
* eval.c (maybe_signal_error_2):
* eval.c (signal_continuable_error_2):
* eval.c (maybe_signal_continuable_error_2):
* eval.c (signal_ferror):
* eval.c (maybe_signal_ferror):
* eval.c (signal_continuable_ferror):
* eval.c (maybe_signal_continuable_ferror):
* eval.c (signal_ferror_with_frob):
* eval.c (maybe_signal_ferror_with_frob):
* eval.c (signal_continuable_ferror_with_frob):
* eval.c (maybe_signal_continuable_ferror_with_frob):
* eval.c (syntax_error):
* eval.c (syntax_error_2):
* eval.c (maybe_syntax_error):
* eval.c (sferror):
* eval.c (sferror_2):
* eval.c (maybe_sferror):
* eval.c (invalid_argument):
* eval.c (invalid_argument_2):
* eval.c (maybe_invalid_argument):
* eval.c (invalid_constant):
* eval.c (invalid_constant_2):
* eval.c (maybe_invalid_constant):
* eval.c (invalid_operation):
* eval.c (invalid_operation_2):
* eval.c (maybe_invalid_operation):
* eval.c (invalid_change):
* eval.c (invalid_change_2):
* eval.c (maybe_invalid_change):
* eval.c (invalid_state):
* eval.c (invalid_state_2):
* eval.c (maybe_invalid_state):
* eval.c (wtaerror):
* eval.c (stack_overflow):
* eval.c (out_of_memory):
* eval.c (print_multiple_value):
* eval.c (issue_call_trapping_problems_warning):
* eval.c (backtrace_specials):
* eval.c (backtrace_unevalled_args):
* eval.c (Fbacktrace):
* eval.c (warn_when_safe):
* event-Xt.c (modwarn):
* event-Xt.c (modbarf):
* event-Xt.c (check_modifier):
* event-Xt.c (store_modifier):
* event-Xt.c (emacs_Xt_format_magic_event):
* event-Xt.c (describe_event):
* event-gtk.c (dragndrop_data_received):
* event-gtk.c (store_modifier):
* event-gtk.c (gtk_reset_modifier_mapping):
* event-msw.c (dde_eval_string):
* event-msw.c (Fdde_alloc_advise_item):
* event-msw.c (mswindows_dde_callback):
* event-msw.c (FROB):
* event-msw.c (emacs_mswindows_format_magic_event):
* event-stream.c (external_debugging_print_event):
* event-stream.c (execute_help_form):
* event-stream.c (vars_of_event_stream):
* events.c (print_event_1):
* events.c (print_event):
* events.c (event_equal):
* extents.c (print_extent_1):
* extents.c (print_extent):
* extents.c (vars_of_extents):
* faces.c (print_face):
* faces.c (complex_vars_of_faces):
* file-coding.c:
* file-coding.c (print_coding_system):
* file-coding.c (print_coding_system_in_print_method):
* file-coding.c (default_query_method):
* file-coding.c (find_coding_system):
* file-coding.c (make_coding_system_1):
* file-coding.c (chain_print):
* file-coding.c (undecided_print):
* file-coding.c (gzip_print):
* file-coding.c (vars_of_file_coding):
* file-coding.c (complex_vars_of_file_coding):
* fileio.c:
* fileio.c (report_file_type_error):
* fileio.c (report_error_with_errno):
* fileio.c (report_file_error):
* fileio.c (barf_or_query_if_file_exists):
* fileio.c (vars_of_fileio):
* floatfns.c (matherr):
* fns.c (print_bit_vector):
* fns.c (Fmapconcat):
* fns.c (add_suffix_to_symbol):
* fns.c (add_prefix_to_symbol):
* frame-gtk.c:
* frame-gtk.c (Fgtk_window_id):
* frame-x.c (def):
* frame-x.c (x_cde_transfer_callback):
* frame.c:
* frame.c (Fmake_frame):
* gc.c (show_gc_cursor_and_message):
* gc.c (vars_of_gc):
* glyphs-eimage.c (png_instantiate):
* glyphs-eimage.c (tiff_instantiate):
* glyphs-gtk.c (gtk_print_image_instance):
* glyphs-msw.c (mswindows_print_image_instance):
* glyphs-x.c (x_print_image_instance):
* glyphs-x.c (update_widget_face):
* glyphs.c (make_string_from_file):
* glyphs.c (print_image_instance):
* glyphs.c (signal_image_error):
* glyphs.c (signal_image_error_2):
* glyphs.c (signal_double_image_error):
* glyphs.c (signal_double_image_error_2):
* glyphs.c (xbm_mask_file_munging):
* glyphs.c (pixmap_to_lisp_data):
* glyphs.h:
* gui.c (gui_item_display_flush_left):
* hpplay.c (player_error_internal):
* hpplay.c (myHandler):
* intl-win32.c:
* intl-win32.c (langcode_to_lang):
* intl-win32.c (sublangcode_to_lang):
* intl-win32.c (Fmswindows_get_locale_info):
* intl-win32.c (lcid_to_locale_mule_or_no):
* intl-win32.c (mswindows_multibyte_to_unicode_print):
* intl-win32.c (complex_vars_of_intl_win32):
* keymap.c:
* keymap.c (print_keymap):
* keymap.c (ensure_meta_prefix_char_keymapp):
* keymap.c (Fkey_description):
* keymap.c (Ftext_char_description):
* lisp.h:
* lisp.h (struct):
* lisp.h (DECLARE_INLINE_HEADER):
* lread.c (Fload_internal):
* lread.c (locate_file):
* lread.c (read_escape):
* lread.c (read_raw_string):
* lread.c (read1):
* lread.c (read_list):
* lread.c (read_compiled_function):
* lread.c (init_lread):
* lrecord.h:
* marker.c (print_marker):
* marker.c (marker_equal):
* menubar-msw.c (displayable_menu_item):
* menubar-x.c (command_builder_operate_menu_accelerator):
* menubar.c (vars_of_menubar):
* minibuf.c (reinit_complex_vars_of_minibuf):
* minibuf.c (complex_vars_of_minibuf):
* mule-charset.c (Fmake_charset):
* mule-charset.c (complex_vars_of_mule_charset):
* mule-coding.c (iso2022_print):
* mule-coding.c (fixed_width_query):
* number.c (bignum_print):
* number.c (ratio_print):
* number.c (bigfloat_print):
* number.c (bigfloat_finalize):
* objects-msw.c:
* objects-msw.c (mswindows_color_to_string):
* objects-msw.c (mswindows_color_list):
* objects-tty.c:
* objects-tty.c (tty_font_list):
* objects-tty.c (tty_find_charset_font):
* objects-xlike-inc.c (xft_find_charset_font):
* objects-xlike-inc.c (endif):
* print.c:
* print.c (write_istring):
* print.c (write_ascstring):
* print.c (Fterpri):
* print.c (Fprint):
* print.c (print_error_message):
* print.c (print_vector_internal):
* print.c (print_cons):
* print.c (print_string):
* print.c (printing_unreadable_object):
* print.c (print_internal):
* print.c (print_float):
* print.c (print_symbol):
* process-nt.c (mswindows_report_winsock_error):
* process-nt.c (nt_canonicalize_host_name):
* process-unix.c (unix_canonicalize_host_name):
* process.c (print_process):
* process.c (report_process_error):
* process.c (report_network_error):
* process.c (make_process_internal):
* process.c (Fstart_process_internal):
* process.c (status_message):
* process.c (putenv_internal):
* process.c (vars_of_process):
* process.h:
* profile.c (vars_of_profile):
* rangetab.c (print_range_table):
* realpath.c (vars_of_realpath):
* redisplay.c (vars_of_redisplay):
* search.c (wordify):
* search.c (Freplace_match):
* sheap.c (sheap_adjust_h):
* sound.c (report_sound_error):
* sound.c (Fplay_sound_file):
* specifier.c (print_specifier):
* symbols.c (Fsubr_name):
* symbols.c (do_symval_forwarding):
* symbols.c (set_default_buffer_slot_variable):
* symbols.c (set_default_console_slot_variable):
* symbols.c (store_symval_forwarding):
* symbols.c (default_value):
* symbols.c (defsymbol_massage_name_1):
* symbols.c (defsymbol_massage_name_nodump):
* symbols.c (defsymbol_massage_name):
* symbols.c (defsymbol_massage_multiword_predicate_nodump):
* symbols.c (defsymbol_massage_multiword_predicate):
* symbols.c (defsymbol_nodump):
* symbols.c (defsymbol):
* symbols.c (defkeyword):
* symbols.c (defkeyword_massage_name):
* symbols.c (check_module_subr):
* symbols.c (deferror_1):
* symbols.c (deferror):
* symbols.c (deferror_massage_name):
* symbols.c (deferror_massage_name_and_message):
* symbols.c (defvar_magic):
* symeval.h:
* symeval.h (DEFVAR_SYMVAL_FWD):
* sysdep.c:
* sysdep.c (init_system_name):
* sysdll.c:
* sysdll.c (MAYBE_PREPEND_UNDERSCORE):
* sysdll.c (dll_function):
* sysdll.c (dll_variable):
* sysdll.c (dll_error):
* sysdll.c (dll_open):
* sysdll.c (dll_close):
* sysdll.c (image_for_address):
* sysdll.c (my_find_image):
* sysdll.c (search_linked_libs):
* sysdll.h:
* sysfile.h:
* sysfile.h (DEFAULT_DIRECTORY_FALLBACK):
* syswindows.h:
* tests.c (DFC_CHECK_LENGTH):
* tests.c (DFC_CHECK_CONTENT):
* tests.c (Ftest_hash_tables):
* text.c (vars_of_text):
* text.h:
* tooltalk.c (tt_opnum_string):
* tooltalk.c (tt_message_arg_ival_string):
* tooltalk.c (Ftooltalk_default_procid):
* tooltalk.c (Ftooltalk_default_session):
* tooltalk.c (init_tooltalk):
* tooltalk.c (vars_of_tooltalk):
* ui-gtk.c (Fdll_load):
* ui-gtk.c (type_to_marshaller_type):
* ui-gtk.c (Fgtk_import_function_internal):
* ui-gtk.c (emacs_gtk_object_printer):
* ui-gtk.c (emacs_gtk_boxed_printer):
* unicode.c (unicode_to_ichar):
* unicode.c (unicode_print):
* unicode.c (unicode_query):
* unicode.c (vars_of_unicode):
* unicode.c (complex_vars_of_unicode):
* win32.c:
* win32.c (mswindows_report_process_error):
* window.c (print_window):
* xemacs.def.in.in:
BASIC IDEA: Further fixing up uses of char * and CIbyte *
to reflect their actual semantics; Mule-izing some code;
redoing of the not-yet-working code to handle message translation.
Clean up code to handle message-translation (not yet working).
Create separate versions of build_msg_string() for working with
Ibyte *, CIbyte *, and Ascbyte * arguments. Assert that Ascbyte *
arguments are pure-ASCII. Make build_msg_string() be the same
as build_msg_ascstring(). Create same three versions of GETTEXT()
and DEFER_GETTEXT(). Also create build_defer_string() and
variants for the equivalent of DEFER_GETTEXT() when building a
string. Remove old CGETTEXT(). Clean up code where GETTEXT(),
DEFER_GETTEXT(), build_msg_string(), etc. was being called and
introduce some new calls to build_msg_string(), etc. Remove
GETTEXT() from calls to weird_doc() -- we assume that the
message snarfer knows about weird_doc(). Remove uses of
DEFER_GETTEXT() from error messages in sysdep.c and instead use
special comments /* @@@begin-snarf@@@ */ and /* @@@end-snarf@@@ */
that the message snarfer presumably knows about.
Create build_ascstring() and use it in many instances in place
of build_string(). The purpose of having Ascbyte * variants is
to make the code more self-documenting in terms of what sort of
semantics is expected for char * strings. In fact in the process
of looking for uses of build_string(), much improperly Mule-ized
was discovered.
Mule-ize a lot of code as described in previous paragraph,
e.g. in sysdep.c.
Make the error functions take Ascbyte * strings and fix up a
couple of places where non-pure-ASCII strings were being passed in
(file-coding.c, mule-coding.c, unicode.c). (It's debatable whether
we really need to make the error functions work this way. It
helps catch places where code is written in a way that message
translation won't work, but we may well never implement message
translation.)
Make staticpro() and friends take Ascbyte * strings instead of
raw char * strings. Create a const_Ascbyte_ptr dynarr type
to describe what's held by staticpro_names[] and friends,
create pdump descriptions for const_Ascbyte_ptr dynarrs, and
use them in place of specially-crafted staticpro descriptions.
Mule-ize certain other functions (e.g. x_event_name) by correcting
raw use of char * to Ascbyte *, Rawbyte * or another such type,
and raw use of char[] buffers to another type (usually Ascbyte[]).
Change many uses of write_c_string() to write_msg_string(),
write_ascstring(), etc.
Mule-ize emodules.c, emodules.h, sysdll.h.
Fix some un-Mule-ized code in intl-win32.c.
A comment in event-Xt.c and the limitations of the message
snarfer (make-msgfile or whatever) is presumably incorrect --
it should be smart enough to handle function calls spread over
more than one line. Clean up code in event-Xt.c that was
written awkwardly for this reason.
In config.h.in, instead of NEED_ERROR_CHECK_TYPES_INLINES,
create a more general XEMACS_DEFS_NEEDS_INLINE_DECLS to
indicate when inlined functions need to be declared in
xemacs.defs.in.in, and make use of it in xemacs.defs.in.in.
We need to do this because postgresql.c now calls qxestrdup(),
which is an inline function.
Make nconc2() and other such functions MODULE_API and put
them in xemacs.defs.in.in since postgresql.c now uses them.
Clean up indentation in lread.c and a few other places.
In text.h, document ASSERT_ASCTEXT_ASCII() and
ASSERT_ASCTEXT_ASCII_LEN(), group together the stand-in
encodings and add some more for DLL symbols, function and
variable names, etc.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Tue, 26 Jan 2010 23:22:30 -0600 |
| parents | facf3239ba30 |
| children | 16112448d484 |
line wrap: on
line source
/* Image processing functions Copyright (C) 1998 Jareth Hein This file is a part of XEmacs XEmacs is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. XEmacs is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with XEmacs; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /* Synched up with: Not in FSF. */ /* Original author: Jareth Hein */ /* Parts of this file are based on code from Sam Leffler's tiff library, with the original copyright displayed here: Copyright (c) 1988-1997 Sam Leffler Copyright (c) 1991-1997 Silicon Graphics, Inc. Permission to use, copy, modify, distribute, and sell this software and its documentation for any purpose is hereby granted without fee, provided that (i) the above copyright notices and this permission notice appear in all copies of the software and related documentation, and (ii) the names of Sam Leffler and Silicon Graphics may not be used in any advertising or publicity relating to the software without the specific, prior written permission of Sam Leffler and Silicon Graphics. */ /* Quantizing code based off of the paper Color Image Quantization for Frame Buffer Display, Paul Heckbert, Siggraph '82 proceedings, pp. 297-307 */ #include <config.h> #include "lisp.h" #include "imgproc.h" static void get_histogram(quant_table *qt, Binbyte *pic, int width, int height, Colorbox* box) { register Binbyte *inptr; register int red, green, blue; register int j, i; box->rmin = box->gmin = box->bmin = 999; box->rmax = box->gmax = box->bmax = -1; box->total = width * height; inptr = pic; for (i = 0; i < height; i++) { for (j = width; j-- > 0;) { red = *inptr++ >> COLOR_SHIFT; green = *inptr++ >> COLOR_SHIFT; blue = *inptr++ >> COLOR_SHIFT; if (red < box->rmin) box->rmin = red; if (red > box->rmax) box->rmax = red; if (green < box->gmin) box->gmin = green; if (green > box->gmax) box->gmax = green; if (blue < box->bmin) box->bmin = blue; if (blue > box->bmax) box->bmax = blue; qt->histogram[red][green][blue]++; } } } static Colorbox * largest_box(quant_table *qt) { register Colorbox *p, *b; register int size; b = NULL; size = -1; for (p = qt->usedboxes; p != NULL; p = p->next) if ((p->rmax > p->rmin || p->gmax > p->gmin || p->bmax > p->bmin) && p->total > size) size = (b = p)->total; return (b); } static void shrinkbox(quant_table *qt, Colorbox* box) { register int *histp, ir, ig, ib; if (box->rmax > box->rmin) { for (ir = box->rmin; ir <= box->rmax; ++ir) for (ig = box->gmin; ig <= box->gmax; ++ig) { histp = &(qt->histogram[ir][ig][box->bmin]); for (ib = box->bmin; ib <= box->bmax; ++ib) if (*histp++ != 0) { box->rmin = ir; goto have_rmin; } } have_rmin: if (box->rmax > box->rmin) for (ir = box->rmax; ir >= box->rmin; --ir) for (ig = box->gmin; ig <= box->gmax; ++ig) { histp = &(qt->histogram[ir][ig][box->bmin]); ib = box->bmin; for (; ib <= box->bmax; ++ib) if (*histp++ != 0) { box->rmax = ir; goto have_rmax; } } } have_rmax: if (box->gmax > box->gmin) { for (ig = box->gmin; ig <= box->gmax; ++ig) for (ir = box->rmin; ir <= box->rmax; ++ir) { histp = &(qt->histogram[ir][ig][box->bmin]); for (ib = box->bmin; ib <= box->bmax; ++ib) if (*histp++ != 0) { box->gmin = ig; goto have_gmin; } } have_gmin: if (box->gmax > box->gmin) for (ig = box->gmax; ig >= box->gmin; --ig) for (ir = box->rmin; ir <= box->rmax; ++ir) { histp = &(qt->histogram[ir][ig][box->bmin]); ib = box->bmin; for (; ib <= box->bmax; ++ib) if (*histp++ != 0) { box->gmax = ig; goto have_gmax; } } } have_gmax: if (box->bmax > box->bmin) { for (ib = box->bmin; ib <= box->bmax; ++ib) for (ir = box->rmin; ir <= box->rmax; ++ir) { histp = &(qt->histogram[ir][box->gmin][ib]); for (ig = box->gmin; ig <= box->gmax; ++ig) { if (*histp != 0) { box->bmin = ib; goto have_bmin; } histp += B_LEN; } } have_bmin: if (box->bmax > box->bmin) for (ib = box->bmax; ib >= box->bmin; --ib) for (ir = box->rmin; ir <= box->rmax; ++ir) { histp = &(qt->histogram[ir][box->gmin][ib]); ig = box->gmin; for (; ig <= box->gmax; ++ig) { if (*histp != 0) { box->bmax = ib; goto have_bmax; } histp += B_LEN; } } } have_bmax: ; } static void splitbox(quant_table *qt, Colorbox* ptr) { int hist2[B_LEN]; int first = 0, last = 0; register Colorbox *new_; register int *iptr, *histp; register int i, j; register int ir,ig,ib; register int sum, sum1, sum2; enum { RED, GREEN, BLUE } axis; /* * See which axis is the largest, do a histogram along that * axis. Split at median point. Contract both new boxes to * fit points and return */ i = ptr->rmax - ptr->rmin; if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin) axis = RED; else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin) axis = GREEN; else axis = BLUE; /* get histogram along longest axis */ switch (axis) { case RED: histp = &hist2[ptr->rmin]; for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) { *histp = 0; for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) { iptr = &(qt->histogram[ir][ig][ptr->bmin]); for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) *histp += *iptr++; } histp++; } first = ptr->rmin; last = ptr->rmax; break; case GREEN: histp = &hist2[ptr->gmin]; for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) { *histp = 0; for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) { iptr = &(qt->histogram[ir][ig][ptr->bmin]); for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) *histp += *iptr++; } histp++; } first = ptr->gmin; last = ptr->gmax; break; case BLUE: histp = &hist2[ptr->bmin]; for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) { *histp = 0; for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) { iptr = &(qt->histogram[ir][ptr->gmin][ib]); for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) { *histp += *iptr; iptr += B_LEN; } } histp++; } first = ptr->bmin; last = ptr->bmax; break; } /* find median point */ sum2 = ptr->total / 2; histp = &hist2[first]; sum = 0; for (i = first; i <= last && (sum += *histp++) < sum2; ++i) ; if (i == first) i++; /* Create new box, re-allocate points */ new_ = qt->freeboxes; qt->freeboxes = new_->next; if (qt->freeboxes) qt->freeboxes->prev = NULL; if (qt->usedboxes) qt->usedboxes->prev = new_; new_->next = qt->usedboxes; qt->usedboxes = new_; histp = &hist2[first]; for (sum1 = 0, j = first; j < i; j++) sum1 += *histp++; for (sum2 = 0, j = i; j <= last; j++) sum2 += *histp++; new_->total = sum1; ptr->total = sum2; new_->rmin = ptr->rmin; new_->rmax = ptr->rmax; new_->gmin = ptr->gmin; new_->gmax = ptr->gmax; new_->bmin = ptr->bmin; new_->bmax = ptr->bmax; switch (axis) { case RED: new_->rmax = i-1; ptr->rmin = i; break; case GREEN: new_->gmax = i-1; ptr->gmin = i; break; case BLUE: new_->bmax = i-1; ptr->bmin = i; break; } shrinkbox (qt, new_); shrinkbox (qt, ptr); } static C_cell * create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue) { register int ir, ig, ib, i; register C_cell *ptr; int mindist, next_n; register int tmp, dist, n; ir = red >> (COLOR_DEPTH-C_DEPTH); ig = green >> (COLOR_DEPTH-C_DEPTH); ib = blue >> (COLOR_DEPTH-C_DEPTH); ptr = xnew (C_cell); *(qt->ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr; ptr->num_ents = 0; /* * Step 1: find all colors inside this cell, while we're at * it, find distance of centermost point to furthest corner */ mindist = 99999999; for (i = 0; i < num_colors; ++i) { if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) continue; ptr->entries[ptr->num_ents][0] = i; ptr->entries[ptr->num_ents][1] = 0; ++ptr->num_ents; tmp = qt->rm[i] - red; if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp; dist = tmp*tmp; tmp = qt->gm[i] - green; if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp; dist += tmp*tmp; tmp = qt->bm[i] - blue; if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp; dist += tmp*tmp; if (dist < mindist) mindist = dist; } /* * Step 3: find all points within that distance to cell. */ for (i = 0; i < num_colors; ++i) { if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) continue; dist = 0; if ((tmp = red - qt->rm[i]) > 0 || (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp; if ((tmp = green - qt->gm[i]) > 0 || (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp; if ((tmp = blue - qt->bm[i]) > 0 || (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp; if (dist < mindist) { ptr->entries[ptr->num_ents][0] = i; ptr->entries[ptr->num_ents][1] = dist; ++ptr->num_ents; } } /* * Sort color cells by distance, use cheap exchange sort */ for (n = ptr->num_ents - 1; n > 0; n = next_n) { next_n = 0; for (i = 0; i < n; ++i) if (ptr->entries[i][1] > ptr->entries[i+1][1]) { tmp = ptr->entries[i][0]; ptr->entries[i][0] = ptr->entries[i+1][0]; ptr->entries[i+1][0] = tmp; tmp = ptr->entries[i][1]; ptr->entries[i][1] = ptr->entries[i+1][1]; ptr->entries[i+1][1] = tmp; next_n = i; } } return (ptr); } static int map_colortable(quant_table *qt, int num_colors) { register int *histp = &(qt->histogram[0][0][0]); register C_cell *cell; register int j, tmp, d2, dist; int ir, ig, ib, i; for (ir = 0; ir < B_LEN; ++ir) for (ig = 0; ig < B_LEN; ++ig) for (ib = 0; ib < B_LEN; ++ib, histp++) { if (*histp == 0) { *histp = -1; continue; } cell = *(qt->ColorCells + (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) + ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) + (ib>>(B_DEPTH-C_DEPTH)))); if (cell == NULL ) cell = create_colorcell (qt, num_colors, ir << COLOR_SHIFT, ig << COLOR_SHIFT, ib << COLOR_SHIFT); if (cell == NULL) /* memory exhausted! punt! */ return -1; dist = 9999999; for (i = 0; i < cell->num_ents && dist > cell->entries[i][1]; ++i) { j = cell->entries[i][0]; d2 = qt->rm[j] - (ir << COLOR_SHIFT); d2 *= d2; tmp = qt->gm[j] - (ig << COLOR_SHIFT); d2 += tmp*tmp; tmp = qt->bm[j] - (ib << COLOR_SHIFT); d2 += tmp*tmp; if (d2 < dist) { dist = d2; *histp = j; } } } return 0; } quant_table * build_EImage_quantable(Binbyte *eimage, int width, int height, int num_colors) { quant_table *qt; Colorbox *box_list, *ptr; int i,res; qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table)); if (qt == NULL) return NULL; assert (num_colors < 257 && num_colors > 2); /* * STEP 1: create empty boxes */ qt->usedboxes = NULL; box_list = qt->freeboxes = xnew_array (Colorbox, num_colors); qt->freeboxes[0].next = &(qt->freeboxes[1]); qt->freeboxes[0].prev = NULL; for (i = 1; i < num_colors-1; ++i) { qt->freeboxes[i].next = &(qt->freeboxes[i+1]); qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); } qt->freeboxes[num_colors-1].next = NULL; qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]); /* * STEP 2: get histogram, initialize first box */ ptr = qt->freeboxes; qt->freeboxes = ptr->next; if (qt->freeboxes) qt->freeboxes->prev = NULL; ptr->next = qt->usedboxes; qt->usedboxes = ptr; if (ptr->next) ptr->next->prev = ptr; get_histogram (qt, eimage, width, height, ptr); /* * STEP 3: continually subdivide boxes until no more free * boxes remain or until all colors assigned. */ while (qt->freeboxes != NULL) { ptr = largest_box(qt); if (ptr != NULL) splitbox (qt, ptr); else qt->freeboxes = NULL; } /* * STEP 4: assign colors to all boxes */ for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) { qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; qt->um[i] = ptr->total; } qt->num_active_colors = i; /* We're done with the boxes now */ xfree (box_list, Colorbox *); qt->freeboxes = qt->usedboxes = NULL; /* * STEP 5: scan histogram and map all values to closest color */ /* 5a: create cell list as described in Heckbert */ qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); /* 5b: create mapping from truncated pixel space to color table entries */ res = map_colortable (qt, num_colors); /* 5c: done with ColorCells */ for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) if (qt->ColorCells[i]) xfree (qt->ColorCells[i], C_cell *); xfree (qt->ColorCells, C_cell **); if (res) { /* we failed in memory allocation, so clean up and leave */ xfree(qt, quant_table *); return NULL; } return qt; }