Mercurial > hg > xemacs-beta
annotate 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 |
| 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; | |
| 3025 | 205 register Colorbox *new_; |
| 428 | 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 */ | |
| 3025 | 289 new_ = qt->freeboxes; |
| 290 qt->freeboxes = new_->next; | |
| 428 | 291 if (qt->freeboxes) |
| 292 qt->freeboxes->prev = NULL; | |
| 293 if (qt->usedboxes) | |
| 3025 | 294 qt->usedboxes->prev = new_; |
| 295 new_->next = qt->usedboxes; | |
| 296 qt->usedboxes = new_; | |
| 428 | 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++; | |
| 3025 | 303 new_->total = sum1; |
| 428 | 304 ptr->total = sum2; |
| 305 | |
| 3025 | 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; | |
| 428 | 312 switch (axis) |
| 313 { | |
| 314 case RED: | |
| 3025 | 315 new_->rmax = i-1; |
| 428 | 316 ptr->rmin = i; |
| 317 break; | |
| 318 case GREEN: | |
| 3025 | 319 new_->gmax = i-1; |
| 428 | 320 ptr->gmin = i; |
| 321 break; | |
| 322 case BLUE: | |
| 3025 | 323 new_->bmax = i-1; |
| 428 | 324 ptr->bmin = i; |
| 325 break; | |
| 326 } | |
| 3025 | 327 shrinkbox (qt, new_); |
| 428 | 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 } |