home *** CD-ROM | disk | FTP | other *** search
- /* The GIMP -- an image manipulation program
- * Copyright (C) 1995 Spencer Kimball and Peter Mattis
- *
- * This program 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 of the License, or
- * (at your option) any later version.
- *
- * This program 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 this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- */
-
- /*
- * TODO for Convert:
- *
- * Use palette of another open INDEXED image
- *
- * Do error-splitting trick for GREY->INDEXED
- */
-
- /*
- * 2000/01/30 - Use palette_selector instead of option_menu for custom
- * palette. Use libgimp callback functions. [Sven]
- *
- * 99/09/01 - Created a low-bleed FS-dither option. [Adam]
- *
- * 99/08/29 - Deterministic colour dithering to arbitrary palettes.
- * Ideal for animations that are going to be delta-optimized or simply
- * don't want to look 'busy' in static areas. Also a bunch of bugfixes
- * and tweaks. [Adam]
- *
- * 99/08/28 - Deterministic alpha dithering over layers, reduced bleeding
- * of transparent values into opaque values, added optional stage to
- * remove duplicate or unused colour entries from final colourmap. [Adam]
- *
- * 99/02/24 - Many revisions to the box-cut quantizer used in RGB->INDEXED
- * conversion. Box to be cut is chosen on the basis of posessing an axis
- * with the largest sum of weighted perceptible error, rather than based on
- * volume or population. The box is split along this axis rather than its
- * longest axis, at the point of error mean rather than simply at its centre.
- * Error-limiting in the F-S dither has been disabled - it may become optional
- * again later. If you're convinced that you have an image where the old
- * dither looks better, let me know. [Adam]
- *
- * 99/01/10 - Hourglass... [Adam]
- *
- * 98/07/25 - Convert-to-indexed now remembers the last invocation's
- * settings. Also, GRAY->INDEXED more flexible. [Adam]
- *
- * 98/07/05 - Sucked the warning about quantizing to too many colours into
- * a text widget embedded in the dialog, improved intelligence of dialog
- * to default 'custom palette' selection to 'Web' if available, and
- * in this case not bother to present the native WWW-palette radio
- * button. [Adam]
- *
- * 98/04/13 - avoid a division by zero when converting an empty gray-scale
- * image (who would like to do such a thing anyway??) [Sven ]
- *
- * 98/03/23 - fixed a longstanding fencepost - hopefully the *right*
- * way, *again*. [Adam]
- *
- * 97/11/14 - added a proper pdb interface and support for dithering
- * to custom palettes (based on a patch by Eric Hernes) [Yosh]
- *
- * 97/11/04 - fixed the accidental use of the colour-counting case
- * when palette_type is WEB or MONO. [Adam]
- *
- * 97/10/25 - colour-counting implemented (could use some hashing, but
- * performance actually seems okay) - now RGB->INDEXED conversion isn't
- * destructive if it doesn't have to be. [Adam]
- *
- * 97/10/14 - fixed divide-by-zero when converting a completely transparent
- * RGB image to indexed. [Adam]
- *
- * 97/07/01 - started todo/revision log. Put code back in to
- * eliminate full-alpha pixels from RGB histogram.
- * [Adam D. Moss - adam@gimp.org]
- */
-
- #include "config.h"
-
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
-
- #include <glib.h>
-
- #include "apptypes.h"
-
- #include "appenv.h"
- #include "brightness_contrast.h"
- #include "color_balance.h"
- #include "convert.h"
- #include "cursorutil.h"
- #include "curves.h"
- #include "drawable.h"
- #include "floating_sel.h"
- #include "fsdither.h"
- #include "gdisplay.h"
- #include "gimpui.h"
- #include "hue_saturation.h"
- #include "levels.h"
- #include "undo.h"
- #include "palette.h"
- #include "palette_select.h"
- #include "posterize.h"
- #include "threshold.h"
-
- #include "libgimp/gimpcolorspace.h"
- #include "libgimp/gimpmath.h"
-
- #include "libgimp/gimpintl.h"
-
- #include "layer_pvt.h" /* ick. */
- #include "drawable_pvt.h" /* ick ick. */
- #include "tile_manager_pvt.h" /* ick ick ick. */
-
- #define PRECISION_R 6
- #define PRECISION_G 6
- #define PRECISION_B 6
-
- #define HIST_R_ELEMS (1<<PRECISION_R)
- #define HIST_G_ELEMS (1<<PRECISION_G)
- #define HIST_B_ELEMS (1<<PRECISION_B)
-
- #define MR HIST_G_ELEMS*HIST_B_ELEMS
- #define MG HIST_B_ELEMS
-
- #define BITS_IN_SAMPLE 8
-
- #define R_SHIFT (BITS_IN_SAMPLE-PRECISION_R)
- #define G_SHIFT (BITS_IN_SAMPLE-PRECISION_G)
- #define B_SHIFT (BITS_IN_SAMPLE-PRECISION_B)
-
- /* this has to match the INTENSITY definition in libgimp/gimpcolorspace.h */
- #define R_SCALE 30 /* scale R distances by this much */
- #define G_SCALE 59 /* scale G distances by this much */
- #define B_SCALE 11 /* and B by this much */
-
- static const unsigned char webpal[] =
- {
- 255,255,255,255,255,204,255,255,153,255,255,102,255,255,51,255,255,0,255,
- 204,255,255,204,204,255,204,153,255,204,102,255,204,51,255,204,0,255,153,
- 255,255,153,204,255,153,153,255,153,102,255,153,51,255,153,0,255,102,255,
- 255,102,204,255,102,153,255,102,102,255,102,51,255,102,0,255,51,255,255,
- 51,204,255,51,153,255,51,102,255,51,51,255,51,0,255,0,255,255,0,
- 204,255,0,153,255,0,102,255,0,51,255,0,0,204,255,255,204,255,204,
- 204,255,153,204,255,102,204,255,51,204,255,0,204,204,255,204,204,204,204,
- 204,153,204,204,102,204,204,51,204,204,0,204,153,255,204,153,204,204,153,
- 153,204,153,102,204,153,51,204,153,0,204,102,255,204,102,204,204,102,153,
- 204,102,102,204,102,51,204,102,0,204,51,255,204,51,204,204,51,153,204,
- 51,102,204,51,51,204,51,0,204,0,255,204,0,204,204,0,153,204,0,
- 102,204,0,51,204,0,0,153,255,255,153,255,204,153,255,153,153,255,102,
- 153,255,51,153,255,0,153,204,255,153,204,204,153,204,153,153,204,102,153,
- 204,51,153,204,0,153,153,255,153,153,204,153,153,153,153,153,102,153,153,
- 51,153,153,0,153,102,255,153,102,204,153,102,153,153,102,102,153,102,51,
- 153,102,0,153,51,255,153,51,204,153,51,153,153,51,102,153,51,51,153,
- 51,0,153,0,255,153,0,204,153,0,153,153,0,102,153,0,51,153,0,
- 0,102,255,255,102,255,204,102,255,153,102,255,102,102,255,51,102,255,0,
- 102,204,255,102,204,204,102,204,153,102,204,102,102,204,51,102,204,0,102,
- 153,255,102,153,204,102,153,153,102,153,102,102,153,51,102,153,0,102,102,
- 255,102,102,204,102,102,153,102,102,102,102,102,51,102,102,0,102,51,255,
- 102,51,204,102,51,153,102,51,102,102,51,51,102,51,0,102,0,255,102,
- 0,204,102,0,153,102,0,102,102,0,51,102,0,0,51,255,255,51,255,
- 204,51,255,153,51,255,102,51,255,51,51,255,0,51,204,255,51,204,204,
- 51,204,153,51,204,102,51,204,51,51,204,0,51,153,255,51,153,204,51,
- 153,153,51,153,102,51,153,51,51,153,0,51,102,255,51,102,204,51,102,
- 153,51,102,102,51,102,51,51,102,0,51,51,255,51,51,204,51,51,153,
- 51,51,102,51,51,51,51,51,0,51,0,255,51,0,204,51,0,153,51,
- 0,102,51,0,51,51,0,0,0,255,255,0,255,204,0,255,153,0,255,
- 102,0,255,51,0,255,0,0,204,255,0,204,204,0,204,153,0,204,102,
- 0,204,51,0,204,0,0,153,255,0,153,204,0,153,153,0,153,102,0,
- 153,51,0,153,0,0,102,255,0,102,204,0,102,153,0,102,102,0,102,
- 51,0,102,0,0,51,255,0,51,204,0,51,153,0,51,102,0,51,51,
- 0,51,0,0,0,255,0,0,204,0,0,153,0,0,102,0,0,51,0,0,0
- };
-
- /* Note: convert.c code currently makes assumptions about some of the
- below defines, so small fixes are needed if they change... */
- #define DM_WIDTH 128
- #define DM_WIDTHMASK 127
- #define DM_WIDTH_SHIFT 7
- #define DM_HEIGHT 128
- #define DM_HEIGHTMASK 127
- /* This dither table was generated by Raph Levien using patented
- technology (US Patent 5,276,535). The dither table itself is in the
- public domain. */
- static const guchar DM[128][128] =
- {
- { 0, 41, 23, 5, 17, 39, 7, 15, 62, 23, 40, 51, 31, 47, 9, 32, 52, 27, 57, 25, 6, 61, 27, 52, 37, 7, 40, 63, 18, 36, 10, 42, 25, 62, 45, 34, 20, 42, 37, 14, 35, 29, 50, 10, 61, 2, 40, 8, 37, 12, 58, 22, 5, 41, 10, 39, 0, 60, 11, 46, 2, 55, 38, 17, 36, 59, 13, 54, 37, 56, 8, 29, 16, 13, 63, 22, 41, 55, 7, 20, 49, 14, 23, 55, 37, 23, 19, 36, 15, 49, 23, 63, 30, 14, 38, 27, 53, 13, 22, 41, 19, 31, 7, 19, 50, 30, 49, 16, 3, 32, 56, 40, 29, 34, 8, 48, 19, 45, 4, 51, 12, 46, 35, 49, 16, 42, 12, 62 },
- { 30, 57, 36, 54, 47, 34, 52, 27, 43, 4, 28, 7, 17, 36, 62, 13, 44, 7, 18, 48, 33, 21, 44, 14, 30, 47, 12, 33, 5, 55, 31, 58, 13, 30, 4, 17, 52, 10, 60, 26, 46, 0, 39, 27, 42, 22, 47, 25, 60, 32, 9, 38, 48, 17, 59, 30, 49, 18, 34, 25, 51, 19, 5, 48, 21, 8, 28, 46, 1, 32, 41, 19, 54, 47, 37, 18, 28, 11, 44, 30, 39, 56, 2, 33, 8, 42, 61, 28, 58, 8, 46, 9, 41, 4, 58, 7, 21, 48, 59, 10, 52, 14, 42, 57, 12, 25, 7, 53, 42, 24, 11, 50, 17, 59, 42, 2, 36, 60, 32, 17, 63, 29, 21, 7, 59, 32, 24, 39 },
- { 22, 8, 16, 32, 3, 25, 13, 57, 18, 45, 58, 39, 55, 20, 5, 42, 23, 34, 63, 1, 51, 10, 58, 4, 60, 23, 53, 27, 44, 21, 3, 48, 8, 50, 43, 54, 27, 32, 5, 55, 21, 58, 12, 53, 6, 36, 14, 50, 17, 29, 53, 15, 24, 52, 7, 36, 13, 42, 4, 53, 9, 35, 61, 26, 56, 32, 49, 15, 62, 23, 6, 60, 2, 31, 4, 48, 58, 38, 15, 61, 5, 25, 47, 28, 50, 15, 7, 40, 3, 32, 33, 52, 25, 50, 35, 42, 61, 3, 28, 36, 23, 63, 4, 33, 46, 62, 36, 23, 60, 6, 54, 28, 4, 37, 23, 55, 25, 8, 42, 54, 14, 6, 56, 38, 19, 52, 4, 46 },
- { 48, 53, 43, 12, 45, 63, 30, 37, 9, 34, 21, 1, 25, 47, 29, 58, 3, 54, 15, 39, 29, 17, 38, 35, 20, 43, 1, 49, 15, 59, 29, 39, 22, 35, 16, 23, 1, 47, 39, 18, 8, 44, 25, 31, 57, 19, 63, 4, 45, 3, 42, 61, 1, 31, 45, 20, 57, 29, 62, 21, 32, 41, 14, 44, 3, 39, 5, 34, 10, 43, 51, 35, 23, 52, 40, 10, 21, 1, 53, 18, 51, 43, 12, 62, 18, 54, 26, 51, 20, 57, 14, 1, 62, 16, 11, 18, 32, 39, 17, 44, 1, 48, 26, 37, 18, 2, 51, 14, 28, 45, 35, 18, 57, 13, 47, 11, 51, 20, 2, 39, 31, 47, 25, 1, 50, 11, 60, 7 },
- { 18, 28, 1, 56, 21, 10, 51, 2, 46, 54, 14, 61, 11, 50, 13, 38, 19, 31, 45, 9, 55, 24, 47, 5, 54, 9, 62, 11, 35, 8, 51, 14, 57, 6, 63, 40, 58, 14, 51, 28, 62, 34, 15, 48, 1, 41, 30, 35, 55, 21, 34, 11, 49, 37, 8, 52, 4, 23, 15, 43, 1, 58, 11, 23, 53, 16, 55, 26, 58, 18, 27, 12, 45, 14, 25, 63, 42, 33, 27, 35, 9, 31, 21, 38, 1, 44, 34, 12, 48, 38, 21, 44, 29, 47, 26, 53, 1, 46, 54, 8, 59, 29, 11, 55, 22, 41, 33, 20, 39, 1, 48, 9, 44, 32, 5, 62, 29, 44, 57, 23, 10, 58, 34, 43, 15, 37, 26, 33 },
- { 51, 38, 59, 24, 35, 42, 19, 60, 5, 32, 41, 26, 43, 33, 7, 53, 48, 11, 59, 23, 42, 2, 61, 30, 16, 40, 32, 24, 56, 41, 19, 33, 37, 26, 47, 9, 31, 22, 2, 45, 9, 54, 4, 37, 21, 52, 11, 23, 7, 57, 16, 25, 55, 18, 63, 27, 46, 39, 56, 10, 50, 37, 29, 47, 19, 63, 24, 9, 46, 2, 39, 60, 9, 57, 30, 7, 49, 11, 59, 3, 45, 57, 5, 60, 29, 22, 5, 60, 30, 9, 59, 18, 40, 6, 57, 36, 30, 12, 24, 34, 15, 40, 52, 6, 49, 9, 58, 4, 63, 12, 26, 61, 22, 53, 38, 16, 35, 14, 28, 50, 42, 17, 5, 28, 62, 20, 54, 12 },
- { 26, 6, 31, 15, 49, 6, 38, 27, 22, 49, 16, 56, 2, 62, 30, 21, 0, 36, 28, 6, 49, 32, 13, 52, 26, 50, 19, 46, 3, 26, 62, 0, 53, 12, 29, 3, 53, 41, 60, 24, 38, 13, 58, 16, 43, 9, 59, 39, 46, 28, 44, 40, 2, 33, 13, 41, 16, 6, 47, 31, 26, 17, 57, 6, 38, 0, 42, 36, 29, 52, 20, 31, 48, 0, 34, 56, 20, 36, 23, 54, 14, 41, 24, 37, 10, 55, 46, 25, 16, 45, 36, 4, 55, 23, 15, 8, 50, 62, 5, 56, 44, 20, 13, 28, 59, 31, 24, 47, 31, 52, 37, 17, 40, 0, 26, 49, 3, 60, 7, 33, 0, 61, 53, 40, 8, 45, 2, 41 },
- { 16, 63, 43, 4, 61, 24, 56, 13, 53, 8, 36, 12, 24, 41, 16, 46, 60, 26, 52, 39, 14, 57, 21, 37, 0, 45, 7, 59, 38, 17, 43, 10, 45, 20, 61, 43, 19, 11, 33, 17, 50, 32, 23, 61, 28, 49, 26, 0, 18, 51, 5, 60, 22, 58, 29, 0, 59, 34, 19, 62, 3, 52, 7, 44, 30, 59, 13, 50, 15, 62, 7, 17, 38, 22, 44, 15, 40, 4, 47, 28, 33, 17, 49, 16, 51, 40, 10, 56, 0, 53, 13, 49, 28, 38, 60, 21, 43, 19, 37, 27, 3, 51, 34, 39, 0, 45, 15, 43, 10, 21, 3, 55, 8, 33, 59, 10, 41, 18, 52, 24, 46, 20, 30, 13, 58, 22, 36, 57 },
- { 50, 34, 11, 47, 29, 17, 44, 0, 33, 63, 28, 46, 52, 5, 57, 10, 42, 18, 4, 63, 20, 8, 44, 10, 56, 34, 14, 29, 5, 54, 23, 59, 32, 49, 7, 34, 49, 27, 56, 0, 42, 7, 46, 3, 40, 6, 54, 32, 62, 13, 36, 10, 47, 8, 35, 49, 24, 51, 12, 40, 22, 35, 60, 12, 22, 51, 33, 4, 40, 25, 43, 55, 5, 54, 12, 61, 26, 51, 8, 62, 0, 53, 7, 63, 2, 32, 19, 34, 42, 24, 31, 63, 2, 10, 45, 33, 0, 48, 9, 61, 22, 47, 8, 62, 18, 56, 7, 54, 27, 57, 46, 30, 50, 19, 45, 30, 56, 36, 22, 47, 11, 38, 3, 51, 32, 48, 18, 9 },
- { 0, 21, 40, 19, 52, 9, 37, 48, 20, 40, 3, 18, 27, 38, 35, 22, 31, 56, 13, 35, 46, 28, 60, 40, 27, 18, 61, 50, 41, 30, 7, 36, 2, 25, 16, 57, 5, 15, 47, 29, 55, 19, 30, 52, 15, 34, 20, 12, 43, 30, 20, 54, 25, 44, 53, 12, 38, 5, 55, 27, 48, 15, 33, 27, 45, 8, 19, 28, 56, 11, 33, 49, 18, 36, 29, 2, 45, 16, 39, 19, 31, 43, 27, 35, 20, 52, 26, 6, 61, 11, 41, 17, 29, 51, 20, 56, 25, 32, 41, 17, 53, 31, 25, 14, 42, 23, 35, 16, 38, 6, 34, 12, 15, 62, 6, 21, 13, 1, 63, 9, 55, 27, 43, 25, 14, 4, 31, 55 },
- { 44, 29, 61, 2, 35, 58, 26, 15, 60, 10, 51, 59, 14, 55, 8, 50, 2, 44, 25, 51, 1, 33, 16, 4, 48, 36, 2, 21, 12, 57, 48, 13, 51, 55, 40, 28, 37, 62, 8, 39, 12, 63, 36, 10, 59, 24, 56, 47, 9, 50, 41, 1, 32, 17, 6, 21, 61, 30, 9, 43, 1, 54, 41, 2, 54, 37, 48, 61, 1, 46, 21, 3, 58, 24, 50, 32, 60, 10, 57, 25, 46, 12, 59, 4, 45, 13, 57, 47, 27, 39, 5, 58, 47, 14, 35, 4, 52, 13, 60, 6, 36, 10, 45, 55, 4, 50, 29, 2, 61, 50, 25, 58, 44, 24, 36, 42, 54, 28, 40, 32, 16, 56, 6, 62, 46, 39, 60, 23 },
- { 7, 48, 14, 54, 23, 40, 4, 45, 30, 22, 42, 32, 1, 44, 20, 29, 58, 8, 37, 19, 41, 54, 24, 58, 9, 53, 25, 46, 34, 16, 23, 38, 27, 11, 18, 1, 52, 21, 35, 22, 48, 5, 25, 45, 18, 38, 2, 27, 35, 4, 57, 15, 62, 39, 57, 28, 42, 16, 36, 60, 24, 18, 10, 63, 20, 5, 16, 23, 37, 14, 59, 27, 41, 8, 13, 42, 21, 35, 6, 50, 3, 38, 15, 48, 30, 39, 17, 3, 49, 14, 53, 33, 24, 7, 61, 44, 11, 39, 23, 49, 19, 58, 1, 32, 36, 12, 60, 41, 20, 13, 41, 4, 39, 1, 48, 8, 18, 51, 14, 44, 5, 37, 21, 34, 1, 26, 10, 37 },
- { 53, 36, 27, 9, 50, 12, 32, 55, 2, 57, 7, 17, 48, 34, 63, 15, 40, 26, 62, 11, 49, 6, 31, 39, 22, 42, 6, 63, 1, 39, 60, 4, 42, 61, 32, 45, 24, 44, 2, 60, 16, 41, 53, 1, 33, 61, 49, 17, 63, 23, 45, 26, 33, 3, 23, 46, 2, 50, 20, 4, 45, 34, 49, 30, 39, 58, 44, 31, 53, 34, 6, 52, 30, 47, 63, 1, 53, 22, 42, 31, 58, 23, 54, 22, 61, 8, 36, 59, 22, 35, 21, 1, 55, 40, 27, 16, 30, 54, 2, 29, 43, 16, 39, 63, 21, 46, 26, 10, 48, 32, 19, 53, 30, 56, 26, 60, 33, 4, 61, 23, 49, 59, 15, 53, 19, 58, 42, 16 },
- { 20, 5, 59, 46, 25, 62, 7, 19, 43, 25, 37, 61, 11, 24, 4, 54, 12, 52, 3, 32, 17, 61, 12, 47, 15, 55, 18, 31, 53, 28, 9, 50, 21, 6, 55, 9, 58, 14, 54, 26, 33, 7, 31, 58, 13, 21, 8, 42, 29, 6, 37, 11, 48, 52, 14, 60, 11, 39, 56, 32, 14, 58, 7, 26, 17, 4, 42, 8, 11, 47, 19, 38, 10, 17, 26, 37, 9, 55, 28, 13, 18, 40, 6, 33, 1, 43, 25, 11, 51, 7, 62, 43, 18, 37, 3, 57, 45, 9, 38, 58, 5, 52, 27, 7, 17, 53, 5, 57, 37, 2, 63, 9, 22, 15, 11, 38, 25, 45, 35, 0, 28, 10, 41, 30, 50, 8, 31, 57 },
- { 49, 33, 16, 38, 1, 42, 51, 34, 53, 14, 28, 49, 30, 56, 36, 23, 43, 20, 38, 56, 22, 45, 28, 0, 62, 35, 26, 44, 11, 19, 52, 35, 44, 15, 30, 38, 10, 31, 40, 4, 46, 50, 20, 40, 27, 44, 51, 14, 56, 53, 19, 59, 7, 29, 41, 19, 35, 25, 8, 52, 22, 44, 13, 53, 50, 32, 61, 24, 56, 25, 63, 0, 45, 57, 33, 59, 16, 46, 4, 62, 50, 11, 60, 37, 52, 19, 55, 29, 37, 46, 13, 26, 48, 10, 50, 34, 21, 63, 26, 13, 42, 33, 22, 55, 35, 28, 43, 15, 24, 51, 27, 34, 46, 49, 58, 3, 52, 9, 57, 19, 48, 55, 3, 35, 12, 45, 24, 3 },
- { 41, 11, 56, 28, 18, 31, 22, 10, 37, 6, 47, 13, 3, 41, 9, 46, 0, 48, 29, 6, 34, 10, 55, 37, 20, 8, 49, 3, 41, 59, 14, 25, 0, 63, 19, 47, 27, 51, 17, 57, 23, 10, 61, 6, 54, 3, 38, 31, 0, 22, 34, 43, 20, 55, 31, 0, 49, 63, 29, 38, 3, 62, 28, 40, 0, 22, 14, 35, 2, 48, 15, 43, 23, 14, 3, 29, 49, 20, 39, 34, 0, 44, 29, 9, 15, 47, 5, 42, 0, 31, 58, 5, 31, 61, 23, 15, 0, 47, 19, 50, 24, 3, 59, 11, 44, 0, 31, 59, 6, 42, 17, 60, 0, 39, 20, 31, 43, 17, 29, 40, 12, 25, 60, 22, 52, 15, 63, 29 },
- { 20, 52, 8, 44, 62, 4, 59, 49, 17, 63, 21, 39, 60, 18, 52, 27, 33, 59, 14, 51, 59, 43, 24, 5, 51, 30, 57, 17, 32, 5, 37, 56, 48, 34, 42, 3, 60, 5, 36, 13, 43, 37, 18, 34, 25, 12, 59, 24, 47, 36, 11, 50, 3, 38, 9, 58, 16, 5, 43, 18, 47, 10, 37, 18, 59, 46, 29, 52, 40, 12, 34, 28, 56, 36, 53, 7, 43, 8, 24, 52, 26, 17, 56, 43, 24, 32, 63, 20, 57, 16, 22, 52, 36, 8, 41, 56, 29, 32, 54, 7, 35, 57, 14, 48, 20, 62, 13, 39, 53, 29, 8, 45, 13, 29, 7, 61, 14, 54, 6, 63, 38, 32, 18, 43, 2, 39, 6, 47 },
- { 0, 58, 23, 35, 13, 46, 12, 39, 0, 31, 55, 24, 5, 35, 15, 61, 17, 5, 39, 25, 18, 2, 50, 33, 41, 13, 39, 23, 62, 46, 29, 12, 22, 8, 56, 25, 20, 49, 32, 62, 0, 56, 11, 46, 63, 42, 9, 16, 55, 5, 60, 15, 62, 26, 45, 21, 36, 51, 13, 57, 31, 24, 55, 6, 35, 9, 57, 5, 20, 60, 7, 51, 5, 19, 40, 25, 61, 32, 56, 12, 36, 48, 21, 2, 58, 12, 39, 28, 9, 50, 40, 12, 44, 18, 25, 49, 6, 38, 11, 62, 18, 46, 30, 9, 40, 25, 49, 19, 10, 36, 55, 22, 33, 52, 41, 18, 37, 27, 49, 21, 2, 46, 7, 53, 33, 61, 27, 35 },
- { 41, 31, 5, 39, 51, 26, 33, 57, 27, 41, 9, 44, 54, 29, 48, 7, 44, 36, 57, 10, 31, 63, 16, 45, 11, 60, 1, 47, 7, 20, 43, 3, 58, 36, 13, 52, 39, 7, 15, 28, 22, 48, 30, 21, 1, 29, 49, 44, 27, 17, 40, 30, 24, 42, 12, 53, 33, 7, 47, 20, 1, 42, 11, 49, 25, 43, 17, 32, 45, 27, 41, 21, 31, 62, 11, 49, 2, 15, 42, 5, 63, 7, 41, 27, 49, 6, 54, 23, 46, 34, 2, 28, 54, 3, 59, 12, 46, 17, 42, 28, 40, 1, 37, 51, 5, 55, 2, 34, 47, 16, 3, 62, 47, 5, 23, 56, 1, 44, 12, 34, 51, 16, 57, 11, 25, 17, 54, 13 },
- { 60, 26, 55, 18, 3, 60, 20, 6, 52, 15, 50, 19, 32, 11, 23, 53, 26, 21, 1, 47, 42, 27, 8, 58, 21, 27, 53, 36, 26, 54, 31, 50, 17, 30, 45, 1, 29, 59, 44, 53, 41, 4, 35, 58, 51, 19, 32, 4, 52, 34, 48, 8, 51, 5, 56, 2, 25, 61, 27, 38, 54, 27, 62, 21, 51, 1, 39, 62, 10, 50, 1, 58, 13, 47, 38, 18, 35, 54, 22, 51, 30, 19, 59, 34, 14, 32, 44, 4, 60, 15, 52, 62, 20, 43, 30, 35, 21, 60, 4, 52, 12, 24, 61, 18, 30, 42, 23, 61, 25, 50, 27, 38, 11, 59, 12, 35, 50, 30, 59, 24, 8, 42, 28, 37, 48, 9, 44, 21 },
- { 10, 47, 15, 50, 30, 43, 8, 45, 29, 2, 36, 59, 1, 58, 41, 3, 63, 31, 54, 20, 13, 55, 35, 38, 4, 44, 15, 9, 61, 2, 14, 38, 61, 10, 23, 54, 18, 12, 24, 2, 14, 55, 16, 8, 38, 14, 41, 60, 10, 23, 1, 58, 32, 17, 28, 37, 41, 15, 3, 60, 15, 33, 4, 36, 16, 59, 28, 14, 23, 55, 37, 18, 44, 28, 2, 57, 30, 10, 27, 46, 14, 38, 3, 53, 21, 61, 17, 35, 10, 41, 26, 7, 33, 9, 57, 1, 53, 37, 26, 20, 56, 48, 9, 33, 58, 16, 37, 7, 45, 1, 57, 15, 32, 26, 42, 23, 7, 20, 4, 54, 31, 62, 22, 1, 59, 30, 4, 51 },
- { 36, 2, 38, 11, 24, 36, 54, 22, 62, 47, 25, 8, 28, 45, 16, 38, 12, 43, 9, 37, 49, 3, 23, 52, 18, 30, 50, 33, 19, 42, 49, 26, 6, 40, 47, 35, 63, 38, 50, 33, 60, 26, 36, 47, 24, 57, 6, 26, 39, 63, 19, 44, 14, 46, 61, 9, 50, 30, 45, 23, 10, 50, 44, 8, 31, 54, 6, 46, 36, 4, 30, 54, 8, 52, 22, 41, 4, 60, 40, 0, 58, 24, 45, 10, 37, 1, 48, 30, 56, 17, 38, 48, 24, 47, 19, 39, 14, 8, 45, 32, 2, 34, 27, 44, 4, 52, 11, 56, 31, 21, 40, 19, 44, 51, 2, 63, 46, 58, 36, 43, 14, 5, 50, 38, 14, 56, 40, 23 },
- { 61, 46, 32, 63, 54, 1, 14, 34, 12, 40, 18, 49, 37, 10, 61, 30, 51, 24, 60, 7, 29, 40, 62, 11, 46, 58, 6, 56, 24, 10, 34, 52, 21, 59, 16, 3, 27, 5, 20, 46, 9, 40, 7, 62, 2, 30, 53, 15, 48, 10, 28, 35, 54, 6, 21, 34, 18, 55, 7, 40, 57, 19, 26, 60, 41, 13, 24, 51, 19, 61, 9, 25, 34, 15, 63, 11, 45, 17, 20, 47, 33, 8, 31, 62, 43, 26, 53, 7, 24, 59, 0, 13, 55, 4, 62, 27, 51, 31, 63, 15, 58, 7, 54, 14, 46, 22, 28, 43, 12, 63, 8, 54, 5, 17, 39, 33, 15, 10, 27, 17, 47, 34, 19, 45, 27, 12, 33, 17 },
- { 5, 28, 21, 7, 17, 48, 42, 58, 23, 4, 63, 14, 55, 21, 34, 5, 19, 0, 45, 17, 52, 15, 25, 32, 0, 22, 40, 13, 45, 62, 18, 0, 43, 11, 33, 55, 30, 42, 57, 19, 51, 31, 22, 43, 18, 45, 34, 0, 43, 31, 56, 3, 23, 40, 59, 0, 44, 13, 48, 35, 2, 32, 46, 0, 21, 48, 35, 3, 40, 32, 43, 59, 0, 48, 33, 26, 53, 36, 55, 12, 51, 16, 55, 5, 18, 29, 11, 39, 51, 19, 45, 31, 42, 21, 35, 6, 22, 47, 10, 38, 23, 50, 20, 36, 0, 60, 38, 4, 50, 35, 48, 34, 24, 57, 9, 53, 28, 48, 61, 0, 56, 24, 53, 3, 63, 6, 42, 57 },
- { 13, 53, 45, 40, 58, 27, 6, 16, 38, 51, 33, 30, 43, 2, 47, 56, 40, 50, 33, 57, 27, 5, 47, 42, 60, 36, 16, 54, 28, 4, 37, 57, 28, 51, 22, 8, 45, 14, 6, 39, 0, 54, 11, 59, 28, 12, 50, 21, 61, 13, 19, 38, 49, 11, 25, 37, 58, 29, 22, 63, 14, 56, 12, 53, 30, 63, 9, 57, 26, 12, 47, 16, 23, 39, 50, 6, 31, 2, 25, 6, 28, 41, 36, 22, 50, 57, 42, 3, 34, 8, 28, 61, 11, 50, 16, 54, 41, 0, 55, 43, 5, 29, 41, 63, 25, 16, 53, 18, 26, 10, 21, 0, 61, 30, 41, 22, 3, 38, 20, 39, 29, 8, 41, 16, 36, 52, 22, 19 },
- { 55, 34, 0, 25, 10, 32, 56, 44, 28, 0, 57, 7, 26, 53, 23, 8, 13, 35, 22, 12, 36, 60, 20, 8, 14, 29, 48, 2, 41, 49, 23, 13, 39, 7, 48, 58, 25, 53, 34, 62, 28, 16, 48, 4, 37, 56, 27, 5, 36, 52, 46, 7, 62, 33, 52, 11, 17, 53, 5, 28, 41, 24, 38, 17, 5, 39, 20, 45, 15, 56, 5, 38, 60, 8, 14, 57, 21, 48, 62, 39, 59, 13, 1, 60, 9, 32, 16, 63, 44, 25, 52, 15, 36, 2, 60, 29, 12, 33, 25, 17, 59, 45, 13, 8, 49, 32, 6, 40, 59, 29, 45, 37, 13, 47, 6, 55, 30, 45, 9, 52, 13, 59, 25, 47, 32, 1, 49, 30 },
- { 9, 39, 14, 61, 49, 37, 3, 20, 50, 13, 41, 19, 46, 17, 38, 59, 28, 62, 4, 44, 54, 1, 34, 51, 55, 7, 63, 32, 21, 8, 56, 31, 62, 19, 36, 1, 41, 17, 24, 12, 42, 35, 25, 52, 20, 8, 44, 59, 25, 2, 22, 42, 16, 29, 4, 46, 20, 36, 43, 9, 51, 8, 49, 26, 58, 33, 54, 1, 37, 29, 52, 20, 27, 45, 19, 35, 42, 16, 10, 32, 20, 49, 46, 27, 40, 4, 47, 22, 13, 55, 4, 47, 26, 44, 23, 40, 58, 19, 48, 13, 31, 2, 57, 34, 42, 19, 61, 32, 14, 55, 5, 51, 26, 19, 58, 16, 49, 14, 62, 5, 33, 44, 21, 7, 60, 26, 11, 41 },
- { 62, 24, 47, 29, 8, 19, 53, 11, 60, 24, 32, 61, 4, 55, 31, 2, 49, 16, 39, 9, 31, 24, 43, 17, 26, 38, 11, 25, 58, 43, 12, 35, 3, 46, 15, 32, 63, 4, 49, 56, 2, 60, 10, 32, 63, 17, 39, 12, 55, 30, 57, 9, 48, 55, 39, 24, 60, 2, 58, 31, 19, 61, 34, 3, 42, 11, 22, 46, 7, 61, 10, 42, 3, 55, 32, 1, 58, 28, 44, 54, 4, 34, 23, 15, 56, 20, 37, 58, 6, 30, 38, 18, 63, 9, 32, 5, 51, 3, 62, 37, 52, 18, 39, 23, 3, 51, 9, 47, 1, 23, 43, 15, 60, 35, 11, 40, 1, 36, 31, 26, 57, 2, 37, 54, 18, 44, 58, 16 },
- { 5, 51, 3, 33, 43, 62, 21, 42, 35, 9, 48, 15, 36, 10, 22, 42, 20, 46, 26, 56, 50, 12, 59, 3, 48, 19, 45, 53, 1, 27, 47, 17, 52, 24, 56, 11, 51, 21, 37, 30, 20, 46, 14, 41, 1, 47, 33, 7, 41, 17, 35, 27, 20, 1, 14, 54, 26, 33, 18, 47, 1, 44, 14, 59, 16, 52, 28, 18, 49, 31, 25, 34, 63, 13, 51, 24, 9, 50, 3, 23, 38, 63, 7, 52, 29, 46, 11, 33, 50, 22, 57, 36, 1, 57, 49, 17, 39, 28, 9, 35, 6, 27, 53, 15, 55, 30, 24, 58, 36, 41, 11, 52, 32, 3, 44, 25, 62, 23, 51, 15, 42, 22, 50, 10, 39, 4, 31, 35 },
- { 46, 22, 57, 17, 12, 39, 26, 5, 31, 59, 1, 45, 27, 62, 52, 7, 58, 33, 6, 18, 39, 22, 33, 41, 57, 5, 35, 18, 40, 16, 60, 5, 29, 42, 7, 39, 27, 44, 9, 47, 8, 26, 54, 22, 51, 29, 24, 49, 15, 61, 4, 51, 31, 63, 43, 6, 50, 8, 39, 12, 53, 37, 23, 30, 40, 6, 62, 43, 14, 53, 2, 49, 7, 36, 17, 41, 61, 37, 18, 56, 11, 18, 44, 35, 2, 19, 61, 0, 41, 14, 8, 30, 43, 12, 24, 46, 14, 54, 42, 21, 44, 61, 10, 46, 37, 11, 44, 7, 18, 63, 20, 29, 7, 49, 28, 54, 8, 43, 4, 48, 18, 63, 12, 29, 48, 24, 59, 20 },
- { 13, 36, 28, 54, 35, 2, 56, 46, 16, 49, 22, 40, 11, 34, 14, 43, 29, 12, 63, 48, 2, 61, 7, 15, 28, 30, 50, 9, 61, 33, 38, 23, 54, 13, 61, 33, 3, 59, 16, 35, 58, 40, 5, 38, 13, 57, 3, 58, 37, 21, 45, 12, 39, 7, 35, 30, 13, 56, 22, 62, 27, 6, 55, 10, 48, 21, 33, 2, 38, 23, 40, 20, 44, 29, 59, 4, 26, 12, 33, 47, 28, 53, 31, 13, 59, 41, 27, 49, 26, 54, 45, 16, 53, 21, 35, 7, 59, 26, 11, 56, 1, 24, 33, 4, 28, 62, 21, 49, 31, 2, 56, 39, 24, 58, 13, 17, 37, 21, 56, 10, 38, 0, 34, 55, 15, 43, 1, 52 },
- { 42, 9, 50, 6, 25, 60, 14, 38, 10, 29, 53, 18, 57, 3, 25, 51, 0, 53, 25, 17, 29, 37, 52, 46, 0, 62, 14, 37, 4, 50, 10, 44, 0, 46, 20, 25, 50, 19, 55, 0, 23, 31, 62, 34, 11, 45, 19, 32, 0, 53, 10, 59, 23, 47, 18, 60, 42, 28, 37, 3, 50, 15, 35, 44, 0, 51, 27, 60, 9, 57, 16, 58, 11, 22, 46, 15, 53, 48, 7, 42, 0, 60, 5, 49, 24, 54, 9, 17, 39, 5, 34, 62, 3, 40, 60, 31, 0, 47, 29, 16, 49, 39, 59, 17, 50, 0, 40, 13, 53, 38, 16, 46, 0, 42, 34, 60, 2, 53, 29, 31, 58, 46, 27, 6, 61, 8, 37, 28 },
- { 0, 63, 21, 40, 45, 18, 51, 23, 63, 34, 6, 43, 28, 38, 55, 19, 40, 35, 8, 41, 54, 10, 21, 32, 39, 23, 53, 26, 55, 28, 22, 63, 30, 34, 9, 48, 6, 38, 29, 43, 49, 6, 18, 52, 27, 61, 9, 43, 28, 42, 33, 26, 56, 3, 51, 23, 0, 48, 16, 45, 32, 25, 63, 20, 57, 17, 42, 12, 35, 47, 5, 31, 39, 56, 6, 30, 34, 21, 61, 25, 14, 40, 22, 38, 15, 6, 36, 56, 20, 60, 25, 12, 51, 27, 10, 56, 42, 20, 36, 63, 32, 6, 21, 41, 12, 34, 60, 26, 5, 48, 27, 10, 62, 19, 6, 47, 39, 14, 45, 7, 24, 17, 41, 32, 23, 51, 19, 56 },
- { 45, 31, 15, 59, 4, 33, 7, 47, 0, 41, 13, 61, 4, 47, 9, 23, 60, 14, 57, 31, 4, 45, 59, 6, 58, 10, 44, 20, 8, 42, 15, 6, 55, 17, 58, 31, 53, 12, 61, 10, 15, 57, 43, 2, 23, 35, 48, 14, 54, 6, 18, 49, 15, 38, 11, 34, 62, 9, 21, 58, 11, 41, 4, 31, 38, 8, 29, 55, 19, 36, 27, 52, 0, 25, 50, 43, 1, 39, 8, 55, 35, 51, 10, 30, 45, 62, 29, 2, 46, 10, 32, 48, 18, 38, 5, 22, 33, 8, 51, 3, 14, 44, 54, 25, 57, 30, 18, 52, 33, 22, 59, 28, 36, 52, 32, 21, 26, 50, 5, 55, 35, 60, 14, 54, 4, 40, 16, 33 },
- { 27, 3, 49, 10, 30, 40, 55, 27, 57, 24, 52, 21, 32, 17, 60, 30, 5, 44, 27, 49, 19, 34, 13, 24, 43, 36, 3, 49, 31, 59, 37, 48, 26, 41, 2, 41, 14, 36, 21, 32, 40, 26, 13, 49, 55, 5, 16, 40, 25, 60, 36, 1, 63, 29, 17, 44, 25, 40, 52, 5, 29, 47, 54, 13, 46, 24, 60, 4, 51, 22, 63, 14, 45, 18, 12, 62, 17, 57, 19, 42, 3, 26, 58, 48, 1, 21, 40, 52, 23, 37, 44, 1, 29, 58, 43, 50, 15, 61, 19, 45, 58, 28, 7, 48, 2, 46, 8, 42, 3, 55, 8, 50, 12, 4, 55, 10, 63, 33, 20, 40, 11, 3, 46, 20, 48, 26, 61, 11 },
- { 44, 56, 24, 36, 53, 19, 12, 37, 16, 44, 7, 36, 49, 54, 11, 37, 48, 21, 15, 1, 62, 25, 47, 56, 16, 18, 51, 12, 40, 1, 24, 11, 52, 16, 23, 59, 28, 1, 45, 53, 4, 60, 37, 21, 39, 30, 63, 20, 52, 10, 30, 45, 8, 41, 54, 4, 57, 7, 34, 55, 36, 18, 23, 59, 2, 48, 11, 32, 44, 1, 41, 8, 33, 54, 38, 23, 30, 46, 6, 29, 62, 18, 32, 16, 55, 34, 14, 11, 61, 7, 55, 16, 53, 13, 23, 2, 55, 37, 26, 10, 33, 23, 36, 16, 38, 22, 56, 15, 24, 43, 35, 17, 44, 40, 25, 46, 16, 1, 57, 25, 49, 36, 28, 62, 9, 35, 7, 53 },
- { 17, 38, 8, 61, 1, 50, 26, 62, 3, 31, 56, 15, 1, 26, 40, 2, 34, 51, 56, 36, 42, 9, 38, 2, 29, 60, 32, 57, 19, 62, 34, 47, 4, 57, 39, 7, 44, 63, 24, 18, 46, 28, 8, 54, 1, 34, 7, 46, 3, 37, 50, 23, 57, 21, 13, 46, 31, 20, 43, 15, 1, 61, 8, 33, 37, 17, 56, 26, 15, 49, 24, 59, 28, 3, 56, 9, 52, 32, 13, 49, 10, 43, 5, 45, 8, 25, 59, 42, 28, 33, 19, 40, 8, 63, 35, 47, 25, 4, 40, 52, 1, 60, 12, 53, 63, 9, 29, 60, 37, 19, 1, 62, 31, 20, 58, 12, 41, 30, 43, 9, 18, 52, 22, 1, 39, 30, 58, 21 },
- { 13, 47, 29, 18, 43, 34, 5, 48, 20, 42, 10, 45, 30, 58, 20, 63, 24, 11, 6, 28, 54, 14, 22, 52, 41, 7, 26, 5, 45, 15, 53, 13, 35, 27, 18, 50, 12, 33, 5, 56, 10, 17, 45, 24, 59, 15, 50, 26, 56, 13, 19, 5, 32, 52, 27, 36, 2, 61, 12, 26, 49, 40, 27, 52, 13, 50, 6, 39, 61, 34, 10, 37, 48, 20, 41, 27, 2, 36, 59, 24, 54, 33, 63, 20, 38, 50, 3, 17, 52, 4, 58, 27, 45, 21, 32, 11, 48, 17, 57, 20, 46, 38, 25, 43, 4, 34, 51, 6, 13, 45, 57, 26, 6, 48, 2, 35, 53, 23, 61, 34, 59, 6, 42, 56, 13, 51, 2, 41 },
- { 32, 5, 55, 23, 58, 14, 22, 52, 29, 15, 61, 25, 51, 8, 43, 13, 53, 41, 46, 20, 3, 33, 63, 11, 48, 21, 54, 38, 28, 3, 30, 43, 21, 62, 9, 31, 55, 22, 51, 29, 37, 62, 32, 12, 42, 29, 41, 9, 33, 44, 62, 28, 43, 1, 59, 19, 48, 30, 51, 39, 24, 4, 58, 19, 42, 29, 22, 43, 3, 18, 53, 5, 13, 50, 16, 60, 45, 21, 7, 40, 15, 0, 26, 53, 13, 31, 43, 24, 47, 31, 15, 49, 2, 41, 6, 59, 29, 42, 9, 30, 14, 7, 49, 18, 31, 47, 20, 39, 49, 32, 11, 41, 54, 15, 61, 18, 7, 38, 4, 13, 44, 28, 15, 32, 45, 19, 27, 49 },
- { 63, 34, 11, 39, 2, 45, 37, 8, 59, 39, 33, 4, 36, 17, 48, 5, 29, 18, 32, 61, 39, 50, 5, 27, 35, 0, 46, 12, 22, 49, 60, 6, 54, 0, 38, 49, 2, 42, 15, 40, 0, 47, 20, 51, 3, 57, 18, 61, 22, 0, 39, 16, 55, 12, 35, 8, 41, 22, 6, 59, 16, 45, 10, 36, 0, 62, 9, 54, 30, 58, 21, 43, 63, 31, 7, 35, 12, 48, 58, 28, 47, 37, 41, 9, 57, 20, 61, 0, 36, 11, 57, 35, 23, 52, 37, 18, 0, 62, 22, 55, 35, 62, 27, 54, 0, 15, 61, 28, 2, 59, 22, 9, 37, 27, 33, 51, 29, 48, 19, 50, 25, 37, 10, 57, 5, 37, 60, 8 },
- { 20, 25, 46, 52, 31, 60, 12, 55, 0, 19, 11, 46, 62, 35, 23, 38, 57, 0, 55, 10, 16, 30, 58, 44, 17, 59, 29, 63, 42, 8, 36, 20, 33, 46, 16, 61, 25, 35, 8, 54, 26, 7, 58, 22, 34, 6, 47, 14, 53, 31, 48, 9, 37, 25, 49, 63, 16, 55, 45, 14, 34, 63, 21, 53, 25, 33, 46, 16, 35, 7, 46, 29, 0, 39, 25, 55, 22, 34, 18, 4, 56, 11, 23, 51, 28, 6, 39, 14, 62, 44, 19, 8, 60, 12, 56, 28, 50, 34, 39, 5, 51, 3, 41, 12, 57, 35, 10, 53, 25, 17, 52, 30, 47, 0, 43, 14, 5, 57, 31, 55, 0, 63, 47, 23, 54, 24, 14, 43 },
- { 0, 57, 16, 6, 26, 19, 35, 28, 49, 42, 54, 26, 21, 1, 59, 27, 9, 47, 26, 44, 50, 22, 13, 40, 8, 37, 10, 34, 17, 56, 25, 58, 13, 27, 44, 9, 20, 58, 31, 17, 60, 36, 10, 41, 53, 25, 36, 39, 4, 24, 58, 17, 60, 4, 22, 38, 10, 32, 0, 50, 31, 7, 28, 47, 12, 57, 5, 26, 52, 23, 14, 40, 57, 17, 47, 5, 53, 1, 44, 31, 19, 60, 46, 2, 35, 48, 30, 54, 22, 5, 51, 39, 25, 31, 4, 43, 14, 9, 45, 16, 24, 44, 19, 29, 40, 23, 44, 7, 38, 42, 4, 63, 12, 54, 23, 59, 22, 42, 8, 15, 40, 21, 8, 34, 3, 41, 30, 50 },
- { 39, 10, 48, 33, 41, 54, 5, 47, 23, 13, 32, 7, 52, 44, 14, 39, 58, 18, 35, 6, 37, 2, 60, 24, 55, 19, 53, 2, 51, 32, 1, 41, 51, 4, 40, 29, 47, 3, 52, 44, 13, 49, 28, 16, 1, 62, 11, 27, 52, 35, 5, 42, 29, 47, 14, 56, 28, 53, 26, 38, 9, 56, 40, 3, 38, 15, 41, 60, 1, 37, 50, 25, 11, 28, 61, 19, 42, 62, 10, 52, 39, 6, 32, 14, 58, 17, 7, 26, 42, 34, 27, 10, 54, 40, 20, 63, 26, 53, 21, 61, 32, 7, 59, 48, 3, 56, 18, 31, 58, 14, 49, 21, 36, 16, 45, 9, 36, 24, 62, 45, 27, 31, 53, 17, 49, 12, 62, 18 },
- { 28, 59, 21, 58, 2, 16, 38, 9, 62, 3, 56, 41, 10, 31, 50, 4, 32, 52, 12, 63, 23, 46, 33, 31, 4, 48, 25, 43, 14, 23, 47, 11, 22, 55, 14, 60, 23, 37, 11, 39, 23, 2, 45, 56, 31, 43, 19, 55, 16, 46, 21, 51, 11, 33, 44, 2, 41, 18, 5, 52, 23, 44, 17, 60, 27, 49, 11, 32, 44, 10, 54, 2, 56, 33, 8, 38, 13, 29, 36, 16, 24, 63, 27, 51, 21, 43, 56, 12, 49, 3, 59, 48, 1, 15, 46, 7, 36, 2, 47, 11, 50, 27, 37, 13, 33, 8, 51, 46, 1, 34, 28, 40, 3, 33, 60, 29, 47, 1, 35, 11, 59, 42, 2, 60, 26, 46, 6, 35 },
- { 4, 43, 9, 29, 36, 63, 24, 44, 20, 50, 30, 17, 60, 22, 16, 43, 25, 3, 42, 19, 51, 15, 8, 54, 42, 15, 61, 5, 39, 57, 18, 61, 31, 48, 34, 2, 50, 19, 57, 5, 63, 33, 19, 38, 13, 27, 48, 7, 32, 61, 2, 26, 58, 6, 24, 50, 13, 61, 42, 20, 62, 2, 35, 20, 51, 4, 62, 18, 23, 58, 20, 31, 43, 15, 51, 45, 26, 50, 4, 55, 45, 3, 35, 9, 38, 1, 32, 61, 20, 45, 17, 33, 24, 57, 29, 51, 22, 58, 38, 30, 15, 1, 54, 21, 63, 43, 26, 12, 24, 56, 8, 60, 50, 19, 5, 52, 13, 54, 17, 50, 4, 16, 36, 12, 32, 56, 22, 54 },
- { 51, 25, 40, 53, 12, 49, 15, 57, 34, 7, 38, 47, 2, 36, 55, 8, 61, 30, 56, 7, 28, 59, 48, 11, 27, 35, 21, 45, 28, 36, 9, 38, 6, 16, 24, 63, 10, 32, 28, 43, 21, 53, 5, 60, 8, 57, 3, 45, 11, 37, 15, 54, 40, 20, 62, 36, 27, 34, 11, 48, 30, 15, 54, 8, 30, 42, 22, 34, 48, 13, 35, 63, 4, 37, 22, 2, 59, 9, 41, 23, 13, 41, 49, 18, 59, 24, 40, 5, 37, 30, 9, 61, 44, 6, 37, 11, 33, 17, 5, 55, 41, 60, 23, 39, 17, 5, 30, 62, 41, 16, 46, 25, 11, 56, 39, 26, 20, 38, 29, 39, 22, 52, 44, 20, 48, 1, 38, 14 },
- { 15, 33, 2, 18, 44, 6, 27, 0, 32, 61, 25, 12, 58, 28, 40, 20, 47, 13, 34, 43, 38, 1, 23, 62, 40, 0, 51, 10, 63, 3, 52, 26, 44, 30, 45, 6, 41, 54, 0, 51, 12, 30, 46, 24, 49, 22, 40, 33, 63, 23, 43, 30, 9, 47, 0, 17, 54, 7, 57, 3, 37, 47, 24, 46, 13, 55, 7, 52, 2, 42, 6, 26, 49, 18, 60, 34, 16, 57, 33, 20, 61, 30, 8, 54, 14, 46, 12, 53, 16, 55, 38, 13, 22, 53, 18, 59, 46, 27, 43, 19, 32, 10, 45, 6, 49, 36, 52, 2, 20, 55, 6, 39, 32, 15, 44, 3, 58, 10, 63, 6, 56, 30, 7, 58, 9, 40, 19, 63 },
- { 10, 47, 61, 23, 55, 31, 52, 42, 17, 45, 4, 51, 27, 6, 15, 53, 0, 49, 26, 10, 56, 18, 36, 6, 20, 58, 32, 30, 13, 49, 19, 56, 0, 59, 12, 53, 27, 17, 38, 25, 48, 9, 15, 36, 14, 30, 59, 17, 0, 50, 8, 58, 18, 56, 31, 45, 21, 41, 29, 19, 60, 6, 32, 59, 0, 36, 29, 39, 19, 59, 46, 12, 55, 30, 10, 47, 24, 3, 28, 48, 0, 55, 44, 27, 33, 4, 63, 29, 49, 0, 26, 50, 34, 2, 42, 14, 0, 62, 9, 56, 3, 52, 28, 34, 58, 9, 20, 48, 37, 32, 22, 53, 0, 62, 27, 49, 34, 46, 21, 33, 41, 14, 25, 37, 53, 29, 31, 45 },
- { 56, 28, 7, 37, 11, 36, 20, 9, 54, 14, 39, 19, 34, 63, 45, 37, 24, 17, 60, 31, 21, 45, 53, 29, 47, 15, 7, 55, 40, 23, 34, 14, 42, 20, 37, 35, 15, 59, 7, 62, 34, 40, 59, 1, 51, 42, 10, 28, 54, 21, 35, 5, 38, 13, 36, 4, 59, 12, 39, 53, 15, 43, 9, 21, 39, 62, 16, 56, 25, 9, 32, 38, 0, 41, 14, 51, 40, 53, 43, 11, 37, 17, 5, 22, 57, 39, 19, 7, 42, 21, 60, 10, 31, 63, 25, 52, 30, 49, 36, 25, 48, 17, 61, 14, 22, 42, 29, 13, 60, 11, 47, 18, 35, 41, 7, 23, 4, 16, 51, 11, 0, 48, 61, 3, 17, 50, 5, 24 },
- { 0, 42, 21, 49, 60, 3, 57, 40, 29, 48, 23, 56, 42, 11, 22, 5, 59, 39, 4, 50, 3, 41, 12, 57, 25, 50, 44, 18, 4, 46, 7, 62, 33, 50, 4, 56, 21, 32, 43, 18, 3, 23, 55, 34, 20, 4, 53, 38, 12, 46, 29, 52, 25, 61, 23, 51, 26, 46, 1, 34, 25, 57, 28, 51, 26, 11, 50, 3, 44, 28, 53, 21, 57, 27, 62, 6, 31, 19, 8, 63, 26, 59, 36, 47, 15, 29, 50, 25, 35, 47, 18, 41, 4, 48, 8, 40, 12, 23, 6, 44, 13, 40, 1, 31, 55, 0, 61, 43, 4, 50, 26, 58, 9, 53, 24, 61, 42, 55, 31, 43, 57, 20, 34, 27, 43, 8, 59, 39 },
- { 18, 51, 30, 13, 26, 16, 46, 22, 2, 59, 8, 30, 1, 48, 33, 51, 29, 9, 46, 16, 62, 14, 33, 2, 38, 9, 27, 60, 37, 26, 53, 17, 28, 10, 24, 46, 2, 49, 8, 57, 29, 45, 6, 26, 62, 44, 18, 25, 61, 3, 42, 14, 49, 10, 43, 6, 17, 32, 63, 10, 49, 4, 40, 14, 45, 33, 22, 37, 12, 61, 5, 17, 43, 7, 23, 37, 15, 58, 49, 13, 39, 21, 10, 52, 1, 62, 9, 56, 12, 2, 58, 28, 36, 16, 56, 28, 56, 35, 20, 63, 24, 37, 51, 8, 45, 25, 16, 33, 27, 38, 2, 44, 13, 30, 17, 36, 12, 26, 5, 18, 28, 47, 13, 60, 23, 45, 13, 33 },
- { 55, 4, 62, 34, 52, 38, 7, 63, 32, 37, 13, 53, 25, 62, 18, 12, 55, 41, 27, 35, 24, 49, 31, 52, 17, 63, 34, 1, 56, 12, 41, 2, 48, 58, 39, 16, 61, 27, 41, 52, 13, 19, 50, 39, 11, 31, 57, 6, 32, 40, 20, 55, 1, 28, 33, 57, 48, 8, 37, 22, 44, 18, 53, 1, 61, 5, 54, 16, 47, 36, 50, 24, 55, 34, 48, 45, 1, 30, 33, 46, 2, 50, 32, 42, 25, 34, 43, 21, 38, 52, 23, 45, 14, 54, 21, 4, 44, 16, 53, 29, 10, 47, 19, 57, 12, 54, 39, 10, 51, 15, 63, 21, 57, 40, 51, 1, 48, 57, 37, 62, 2, 38, 9, 52, 1, 35, 58, 22 },
- { 36, 46, 10, 42, 1, 27, 43, 15, 50, 21, 45, 16, 41, 3, 35, 44, 20, 1, 57, 11, 55, 7, 43, 8, 22, 42, 13, 46, 21, 39, 31, 60, 22, 5, 29, 44, 11, 35, 20, 4, 36, 58, 32, 15, 47, 2, 36, 48, 16, 60, 8, 35, 44, 63, 16, 2, 40, 26, 55, 14, 58, 35, 24, 31, 19, 42, 31, 58, 1, 29, 10, 40, 2, 19, 12, 54, 22, 61, 7, 24, 56, 5, 28, 16, 54, 3, 15, 58, 6, 30, 8, 62, 1, 43, 31, 47, 7, 59, 1, 38, 58, 4, 34, 27, 38, 5, 31, 59, 7, 46, 30, 3, 34, 6, 28, 59, 20, 8, 32, 15, 53, 24, 55, 31, 19, 49, 11, 26 },
- { 2, 24, 16, 58, 19, 55, 5, 35, 10, 61, 4, 28, 57, 24, 58, 7, 31, 47, 22, 38, 19, 28, 61, 36, 54, 5, 59, 29, 6, 52, 15, 11, 43, 36, 8, 54, 52, 1, 62, 25, 47, 9, 1, 60, 28, 53, 24, 14, 46, 27, 51, 22, 12, 24, 38, 53, 20, 11, 51, 3, 29, 7, 48, 63, 8, 49, 9, 21, 52, 14, 63, 32, 46, 60, 35, 4, 41, 16, 52, 35, 18, 42, 59, 7, 36, 61, 45, 27, 33, 51, 19, 39, 34, 11, 61, 18, 33, 41, 28, 15, 54, 22, 42, 3, 49, 21, 47, 18, 36, 23, 55, 19, 48, 24, 45, 10, 33, 44, 50, 40, 7, 35, 15, 41, 63, 6, 40, 54 },
- { 62, 41, 32, 8, 47, 28, 60, 24, 44, 30, 38, 49, 9, 33, 14, 40, 50, 14, 60, 2, 54, 40, 0, 20, 25, 39, 16, 49, 24, 35, 57, 47, 19, 61, 33, 18, 23, 37, 13, 55, 31, 43, 22, 41, 17, 8, 42, 58, 0, 37, 5, 56, 31, 54, 7, 30, 60, 33, 42, 17, 59, 39, 12, 27, 38, 17, 35, 41, 27, 45, 20, 7, 25, 15, 29, 58, 27, 47, 11, 40, 14, 54, 23, 46, 19, 31, 11, 40, 13, 49, 5, 58, 24, 51, 26, 6, 50, 20, 49, 9, 32, 46, 17, 60, 14, 63, 24, 1, 57, 41, 9, 43, 14, 62, 16, 52, 3, 27, 14, 22, 61, 45, 4, 28, 9, 47, 29, 17 },
- { 5, 50, 12, 53, 38, 18, 11, 51, 0, 55, 17, 6, 47, 54, 19, 63, 5, 26, 34, 45, 13, 30, 47, 58, 10, 48, 32, 3, 62, 9, 26, 0, 25, 14, 50, 3, 47, 30, 42, 16, 6, 63, 12, 49, 33, 55, 21, 10, 34, 63, 18, 41, 3, 47, 19, 43, 0, 49, 8, 28, 46, 20, 52, 0, 56, 24, 60, 3, 59, 5, 39, 57, 48, 52, 9, 38, 3, 21, 26, 60, 0, 32, 12, 38, 4, 48, 53, 0, 60, 15, 29, 44, 18, 10, 38, 57, 13, 60, 2, 26, 62, 7, 50, 29, 35, 8, 40, 53, 28, 12, 60, 33, 38, 5, 37, 29, 60, 39, 56, 0, 30, 18, 50, 34, 59, 25, 14, 44 },
- { 20, 31, 60, 22, 3, 49, 33, 25, 40, 13, 34, 59, 22, 36, 0, 28, 37, 56, 8, 18, 51, 16, 4, 45, 27, 12, 53, 42, 18, 44, 51, 31, 55, 40, 28, 58, 7, 60, 10, 51, 27, 37, 24, 56, 5, 26, 44, 29, 50, 23, 45, 11, 34, 15, 59, 27, 13, 23, 62, 37, 4, 57, 15, 32, 42, 6, 47, 11, 30, 43, 23, 13, 0, 36, 18, 44, 63, 51, 37, 29, 49, 20, 57, 27, 62, 9, 24, 35, 23, 53, 37, 3, 42, 55, 0, 36, 23, 39, 31, 43, 17, 37, 24, 11, 52, 43, 19, 32, 5, 50, 26, 0, 56, 21, 54, 11, 19, 6, 47, 25, 59, 42, 12, 54, 21, 3, 38, 57 },
- { 48, 0, 35, 27, 44, 14, 59, 7, 57, 46, 26, 2, 42, 12, 52, 43, 10, 27, 53, 42, 32, 62, 37, 21, 34, 61, 7, 23, 36, 4, 38, 12, 41, 5, 17, 45, 22, 27, 39, 21, 59, 0, 45, 18, 39, 62, 3, 38, 14, 7, 54, 26, 61, 39, 9, 52, 45, 36, 18, 50, 10, 34, 44, 22, 50, 14, 36, 55, 17, 34, 53, 62, 33, 26, 56, 6, 31, 12, 6, 53, 9, 44, 2, 50, 20, 40, 55, 17, 47, 7, 26, 63, 22, 32, 48, 16, 46, 8, 52, 12, 57, 41, 0, 56, 25, 3, 61, 14, 45, 35, 18, 44, 12, 46, 23, 42, 32, 51, 35, 10, 17, 36, 23, 1, 45, 52, 32, 10 },
- { 37, 15, 43, 8, 63, 39, 21, 31, 16, 37, 19, 62, 30, 46, 17, 60, 21, 48, 1, 23, 6, 25, 11, 56, 1, 40, 30, 58, 15, 54, 21, 59, 9, 63, 35, 56, 11, 51, 2, 46, 34, 14, 53, 7, 30, 11, 51, 19, 60, 40, 30, 1, 24, 50, 20, 32, 3, 56, 5, 25, 31, 13, 61, 2, 29, 60, 25, 20, 51, 2, 27, 8, 18, 42, 10, 45, 21, 34, 43, 17, 62, 29, 41, 14, 34, 6, 30, 43, 2, 57, 33, 13, 45, 12, 27, 62, 4, 55, 21, 35, 5, 27, 45, 33, 16, 47, 30, 54, 22, 10, 51, 27, 63, 7, 49, 1, 58, 22, 15, 43, 53, 7, 57, 39, 27, 12, 61, 24 },
- { 56, 51, 26, 56, 19, 2, 41, 54, 5, 52, 9, 48, 6, 23, 39, 4, 32, 15, 63, 35, 59, 49, 43, 15, 52, 19, 50, 9, 46, 33, 1, 29, 48, 20, 32, 1, 38, 33, 19, 54, 9, 32, 24, 48, 58, 35, 16, 48, 4, 52, 13, 57, 33, 5, 45, 59, 15, 29, 41, 55, 47, 39, 23, 53, 9, 40, 4, 57, 10, 44, 48, 40, 50, 14, 61, 24, 55, 1, 59, 22, 33, 8, 51, 25, 58, 46, 11, 59, 20, 41, 17, 51, 6, 56, 35, 25, 42, 30, 15, 58, 48, 18, 61, 9, 58, 39, 13, 2, 37, 59, 40, 2, 31, 16, 34, 41, 8, 30, 62, 3, 29, 48, 33, 5, 63, 16, 41, 7 },
- { 22, 4, 46, 11, 33, 51, 29, 10, 62, 24, 43, 27, 15, 58, 50, 25, 54, 44, 9, 38, 18, 3, 29, 57, 32, 5, 26, 43, 17, 61, 24, 52, 8, 42, 23, 53, 15, 61, 7, 28, 57, 43, 4, 40, 20, 2, 43, 25, 32, 35, 21, 43, 17, 48, 10, 22, 38, 54, 11, 21, 1, 58, 16, 30, 48, 18, 46, 32, 38, 13, 22, 4, 59, 35, 2, 51, 30, 39, 15, 47, 4, 56, 13, 37, 1, 28, 16, 52, 32, 9, 61, 29, 38, 19, 3, 52, 10, 48, 1, 32, 11, 40, 20, 36, 6, 22, 49, 29, 55, 6, 20, 56, 36, 52, 19, 60, 26, 46, 18, 54, 40, 13, 20, 46, 35, 19, 49, 29 },
- { 61, 17, 34, 53, 23, 6, 48, 35, 20, 40, 1, 56, 36, 29, 11, 34, 7, 41, 14, 30, 55, 20, 46, 8, 24, 38, 63, 2, 37, 10, 45, 14, 34, 49, 6, 13, 44, 25, 49, 41, 21, 12, 61, 15, 54, 29, 63, 12, 56, 8, 49, 2, 62, 36, 28, 61, 0, 25, 41, 63, 35, 8, 44, 6, 37, 62, 7, 21, 63, 28, 55, 31, 16, 24, 41, 19, 9, 57, 27, 36, 18, 42, 31, 62, 22, 55, 38, 4, 27, 47, 1, 40, 14, 54, 43, 20, 60, 23, 38, 63, 25, 51, 2, 53, 26, 63, 10, 42, 17, 34, 47, 25, 13, 5, 44, 11, 55, 2, 38, 27, 6, 60, 52, 25, 9, 55, 1, 40 },
- { 8, 30, 58, 3, 42, 61, 17, 38, 13, 59, 32, 10, 54, 3, 51, 20, 61, 26, 57, 2, 46, 33, 12, 60, 41, 13, 48, 29, 55, 20, 39, 27, 57, 18, 62, 29, 55, 2, 31, 16, 37, 50, 26, 36, 6, 46, 9, 41, 27, 57, 23, 39, 26, 6, 51, 12, 31, 46, 7, 16, 27, 52, 19, 56, 26, 12, 33, 53, 1, 41, 8, 57, 46, 7, 54, 32, 47, 5, 49, 11, 60, 23, 5, 48, 10, 43, 19, 63, 35, 24, 49, 21, 59, 5, 31, 37, 14, 44, 7, 42, 6, 30, 46, 13, 44, 32, 19, 50, 4, 58, 8, 30, 62, 38, 28, 53, 21, 36, 13, 50, 21, 33, 15, 2, 44, 31, 14, 47 },
- { 37, 13, 39, 16, 28, 9, 57, 0, 25, 49, 21, 45, 18, 47, 12, 42, 0, 49, 22, 39, 16, 53, 25, 36, 0, 52, 22, 16, 6, 60, 4, 51, 0, 26, 37, 47, 10, 36, 63, 5, 57, 0, 18, 59, 23, 33, 51, 19, 0, 44, 15, 11, 54, 17, 42, 35, 53, 18, 58, 33, 49, 4, 34, 42, 0, 50, 43, 25, 16, 49, 34, 20, 37, 28, 12, 63, 16, 38, 25, 44, 0, 40, 52, 17, 35, 3, 50, 14, 8, 53, 11, 36, 25, 45, 9, 62, 0, 54, 28, 17, 50, 55, 15, 24, 57, 0, 53, 34, 23, 41, 15, 45, 0, 49, 16, 4, 48, 9, 63, 45, 0, 42, 58, 37, 61, 22, 54, 26 },
- { 0, 50, 21, 47, 54, 36, 27, 45, 52, 4, 34, 15, 63, 29, 37, 59, 17, 31, 6, 61, 28, 5, 48, 18, 59, 27, 34, 56, 44, 31, 35, 12, 41, 59, 16, 3, 40, 20, 50, 22, 30, 40, 52, 10, 45, 3, 59, 22, 37, 61, 29, 46, 31, 58, 2, 22, 9, 43, 3, 39, 14, 61, 24, 54, 15, 29, 11, 60, 39, 17, 5, 61, 0, 44, 50, 3, 31, 14, 58, 21, 54, 28, 15, 45, 60, 26, 33, 58, 44, 22, 60, 2, 57, 34, 49, 27, 18, 34, 21, 59, 29, 4, 36, 41, 8, 39, 28, 11, 62, 26, 53, 20, 35, 24, 59, 32, 29, 39, 24, 31, 57, 23, 11, 28, 5, 36, 11, 59 },
- { 44, 32, 63, 5, 20, 12, 41, 7, 30, 61, 42, 8, 39, 5, 33, 8, 24, 53, 45, 11, 37, 58, 7, 44, 10, 50, 3, 40, 8, 22, 53, 19, 46, 9, 33, 52, 24, 58, 8, 44, 13, 47, 8, 34, 38, 30, 14, 47, 7, 34, 4, 55, 9, 19, 40, 49, 56, 26, 60, 21, 30, 45, 10, 19, 40, 58, 23, 36, 3, 52, 45, 23, 54, 13, 22, 42, 53, 45, 7, 33, 10, 36, 57, 6, 29, 12, 41, 0, 30, 15, 41, 30, 17, 7, 16, 53, 40, 56, 2, 39, 12, 61, 10, 52, 31, 60, 16, 45, 1, 37, 7, 61, 40, 10, 43, 17, 58, 7, 54, 14, 4, 51, 39, 49, 18, 56, 42, 20 },
- { 14, 6, 24, 36, 56, 49, 22, 60, 18, 14, 23, 51, 26, 57, 21, 52, 41, 14, 35, 50, 19, 31, 40, 23, 33, 14, 63, 17, 32, 47, 7, 62, 23, 30, 56, 11, 42, 27, 14, 60, 35, 19, 28, 61, 17, 55, 25, 39, 53, 17, 42, 21, 38, 63, 25, 5, 14, 36, 12, 50, 1, 37, 59, 32, 2, 51, 6, 56, 27, 32, 11, 30, 38, 26, 60, 8, 26, 19, 62, 39, 50, 2, 21, 39, 53, 23, 56, 19, 49, 39, 5, 46, 55, 23, 42, 4, 31, 11, 47, 26, 45, 22, 48, 18, 21, 5, 48, 25, 57, 14, 47, 30, 3, 56, 12, 50, 1, 42, 19, 47, 35, 17, 8, 30, 45, 25, 4, 51 },
- { 28, 58, 43, 1, 31, 8, 33, 2, 44, 55, 32, 1, 60, 12, 46, 27, 4, 62, 23, 1, 56, 13, 62, 2, 54, 36, 25, 51, 1, 57, 26, 42, 3, 49, 17, 38, 1, 48, 31, 4, 54, 3, 50, 24, 1, 49, 5, 63, 13, 27, 52, 1, 48, 13, 45, 33, 52, 30, 46, 20, 55, 28, 6, 48, 24, 38, 20, 47, 14, 62, 48, 9, 58, 4, 36, 30, 56, 1, 34, 12, 18, 63, 25, 48, 4, 16, 37, 7, 62, 10, 52, 28, 13, 50, 36, 63, 24, 51, 15, 58, 8, 33, 1, 38, 56, 35, 42, 9, 33, 51, 22, 18, 48, 32, 27, 37, 23, 61, 33, 11, 59, 29, 62, 1, 53, 10, 60, 33 },
- { 12, 39, 17, 52, 26, 46, 53, 38, 25, 11, 48, 36, 16, 43, 2, 35, 55, 17, 39, 29, 43, 9, 28, 45, 20, 5, 46, 12, 42, 28, 13, 52, 36, 6, 60, 22, 54, 17, 62, 39, 25, 42, 15, 55, 44, 20, 31, 10, 35, 57, 24, 32, 29, 6, 59, 18, 7, 62, 3, 41, 10, 44, 16, 54, 13, 62, 31, 9, 41, 1, 21, 43, 18, 47, 15, 40, 11, 49, 28, 55, 46, 30, 8, 43, 32, 61, 28, 47, 25, 34, 21, 61, 32, 1, 20, 9, 46, 6, 35, 19, 41, 54, 27, 63, 14, 3, 51, 20, 62, 2, 38, 55, 8, 21, 63, 6, 46, 9, 26, 51, 3, 24, 43, 34, 16, 41, 18, 48 },
- { 62, 23, 55, 9, 15, 62, 19, 13, 58, 40, 6, 30, 54, 19, 50, 31, 10, 44, 6, 59, 21, 47, 51, 15, 60, 39, 30, 54, 21, 61, 19, 33, 14, 29, 43, 11, 34, 45, 7, 21, 10, 56, 36, 6, 38, 11, 58, 42, 2, 47, 11, 60, 50, 16, 41, 28, 38, 23, 47, 17, 35, 63, 22, 33, 42, 5, 45, 17, 53, 35, 25, 56, 33, 6, 51, 19, 60, 23, 43, 15, 5, 40, 58, 13, 51, 1, 45, 11, 54, 3, 43, 8, 37, 48, 59, 29, 39, 21, 61, 43, 3, 31, 10, 44, 24, 29, 60, 12, 28, 40, 11, 25, 43, 52, 14, 41, 16, 57, 44, 20, 40, 55, 12, 21, 57, 27, 35, 2 },
- { 37, 6, 31, 42, 40, 4, 29, 50, 0, 20, 63, 28, 9, 58, 14, 24, 63, 26, 48, 16, 34, 4, 32, 38, 23, 11, 58, 4, 37, 9, 45, 5, 63, 48, 26, 57, 2, 28, 32, 51, 46, 29, 13, 62, 27, 46, 28, 18, 50, 15, 40, 4, 19, 34, 54, 0, 53, 9, 26, 58, 28, 5, 49, 0, 57, 27, 19, 60, 29, 8, 59, 12, 37, 63, 24, 46, 3, 37, 6, 52, 26, 32, 20, 36, 9, 22, 59, 18, 35, 51, 14, 57, 17, 24, 12, 44, 56, 0, 30, 13, 59, 20, 49, 17, 54, 43, 6, 34, 46, 17, 58, 36, 0, 34, 29, 54, 25, 2, 36, 15, 60, 6, 37, 46, 4, 50, 9, 45 },
- { 19, 59, 48, 3, 24, 60, 44, 22, 34, 51, 15, 45, 41, 5, 33, 47, 0, 37, 12, 55, 25, 54, 8, 57, 0, 47, 18, 34, 49, 15, 55, 24, 40, 20, 8, 35, 53, 13, 41, 18, 0, 59, 22, 33, 4, 52, 8, 60, 24, 36, 31, 56, 45, 26, 10, 43, 15, 56, 36, 4, 51, 14, 39, 30, 12, 55, 36, 2, 39, 49, 4, 44, 17, 0, 32, 13, 53, 35, 59, 17, 62, 0, 55, 24, 52, 38, 31, 6, 42, 19, 29, 40, 4, 54, 33, 5, 16, 27, 52, 37, 23, 55, 7, 37, 0, 39, 23, 49, 4, 53, 31, 15, 59, 10, 50, 4, 60, 34, 48, 7, 31, 49, 27, 14, 62, 22, 53, 29 },
- { 46, 21, 14, 51, 36, 17, 7, 57, 10, 32, 3, 37, 22, 60, 39, 18, 56, 20, 42, 3, 36, 10, 44, 26, 41, 29, 53, 27, 2, 39, 30, 52, 0, 59, 15, 48, 23, 61, 6, 58, 37, 12, 40, 49, 16, 39, 20, 44, 0, 62, 8, 21, 3, 59, 23, 32, 49, 31, 12, 44, 22, 59, 18, 50, 24, 7, 43, 52, 15, 23, 41, 26, 51, 28, 55, 39, 21, 27, 10, 42, 12, 45, 27, 47, 3, 15, 63, 26, 55, 0, 60, 26, 45, 18, 62, 38, 58, 49, 8, 47, 4, 33, 46, 29, 57, 13, 56, 16, 59, 21, 5, 47, 23, 39, 18, 44, 13, 22, 28, 53, 19, 0, 58, 32, 41, 7, 26, 13 },
- { 0, 56, 34, 28, 11, 55, 31, 47, 26, 41, 56, 13, 53, 28, 11, 49, 7, 52, 32, 61, 50, 22, 63, 17, 13, 56, 7, 19, 43, 62, 10, 21, 37, 32, 43, 4, 38, 19, 44, 25, 31, 54, 5, 23, 61, 30, 53, 12, 35, 22, 43, 53, 37, 48, 7, 62, 20, 2, 61, 41, 8, 34, 47, 9, 63, 34, 28, 10, 55, 33, 14, 57, 7, 47, 9, 61, 4, 49, 31, 50, 21, 38, 8, 16, 57, 44, 33, 5, 49, 36, 12, 50, 7, 34, 10, 25, 2, 22, 36, 15, 26, 61, 18, 9, 22, 46, 32, 8, 27, 37, 44, 30, 55, 3, 62, 24, 38, 56, 5, 45, 38, 24, 43, 10, 19, 54, 39, 61 },
- { 41, 30, 8, 63, 43, 23, 38, 3, 62, 19, 8, 49, 25, 1, 58, 30, 23, 40, 9, 28, 18, 40, 6, 38, 49, 22, 35, 59, 8, 27, 50, 5, 56, 17, 11, 50, 30, 9, 55, 2, 51, 19, 34, 47, 9, 41, 6, 26, 48, 57, 14, 28, 17, 12, 39, 13, 37, 46, 25, 19, 54, 27, 1, 37, 16, 45, 20, 60, 1, 48, 20, 38, 31, 22, 42, 15, 19, 44, 1, 61, 6, 34, 56, 40, 29, 10, 20, 46, 13, 22, 41, 23, 59, 42, 30, 51, 45, 13, 63, 53, 42, 12, 51, 38, 62, 2, 26, 41, 50, 1, 61, 10, 19, 42, 31, 8, 49, 32, 12, 63, 9, 52, 16, 56, 36, 2, 31, 16 },
- { 52, 5, 47, 20, 1, 53, 12, 50, 16, 35, 43, 21, 33, 43, 16, 44, 3, 59, 14, 46, 1, 30, 60, 33, 2, 45, 12, 42, 31, 47, 14, 33, 46, 25, 55, 27, 60, 36, 16, 42, 14, 46, 26, 1, 55, 15, 63, 32, 2, 38, 5, 47, 33, 61, 30, 52, 4, 57, 6, 38, 11, 43, 61, 24, 52, 3, 31, 22, 42, 10, 62, 3, 59, 11, 35, 57, 33, 54, 24, 14, 29, 48, 18, 2, 60, 41, 53, 24, 32, 62, 3, 53, 15, 1, 55, 17, 32, 40, 6, 31, 1, 40, 28, 5, 35, 52, 19, 63, 13, 33, 17, 41, 52, 26, 15, 57, 1, 20, 42, 17, 35, 27, 48, 5, 25, 50, 44, 11 },
- { 35, 25, 38, 57, 33, 17, 40, 6, 59, 27, 54, 5, 61, 10, 52, 26, 36, 19, 51, 35, 57, 48, 11, 20, 54, 25, 61, 16, 1, 58, 24, 61, 3, 39, 7, 47, 1, 22, 49, 28, 63, 10, 58, 32, 17, 36, 45, 19, 51, 29, 59, 10, 50, 1, 23, 42, 18, 29, 51, 21, 56, 32, 14, 5, 40, 58, 47, 13, 54, 35, 29, 45, 18, 52, 26, 2, 38, 8, 46, 36, 58, 11, 52, 35, 17, 28, 1, 58, 9, 39, 17, 28, 37, 48, 20, 9, 57, 24, 50, 19, 58, 16, 48, 25, 43, 11, 35, 6, 45, 24, 56, 4, 36, 7, 47, 35, 52, 28, 59, 30, 2, 61, 21, 33, 63, 12, 18, 59 },
- { 3, 49, 15, 10, 27, 61, 25, 45, 30, 0, 14, 47, 31, 38, 17, 62, 7, 55, 27, 4, 15, 24, 42, 52, 10, 34, 5, 51, 36, 18, 41, 11, 35, 21, 62, 13, 33, 57, 8, 35, 5, 40, 21, 43, 52, 3, 24, 56, 11, 16, 33, 25, 41, 20, 55, 8, 60, 35, 15, 48, 2, 57, 30, 49, 18, 25, 6, 39, 17, 57, 7, 25, 43, 5, 49, 16, 62, 22, 55, 4, 25, 43, 23, 7, 50, 11, 37, 48, 14, 51, 33, 57, 7, 27, 39, 46, 4, 29, 11, 43, 34, 56, 7, 60, 20, 54, 30, 57, 22, 49, 9, 33, 54, 14, 63, 23, 6, 43, 10, 40, 50, 13, 44, 8, 38, 33, 46, 23 },
- { 55, 39, 22, 50, 44, 4, 36, 9, 52, 23, 37, 59, 21, 2, 46, 13, 31, 41, 11, 45, 62, 29, 6, 37, 19, 48, 30, 23, 44, 7, 53, 28, 54, 16, 41, 29, 44, 18, 52, 24, 60, 15, 48, 7, 27, 59, 9, 34, 42, 54, 7, 63, 4, 46, 31, 27, 45, 0, 40, 26, 34, 17, 37, 10, 53, 29, 36, 50, 2, 27, 51, 11, 61, 37, 23, 41, 30, 7, 18, 50, 39, 14, 63, 32, 45, 61, 19, 30, 25, 44, 2, 47, 23, 63, 11, 34, 59, 37, 60, 3, 22, 14, 44, 30, 15, 0, 47, 15, 3, 38, 61, 20, 27, 45, 11, 39, 51, 16, 55, 3, 22, 54, 29, 58, 1, 57, 6, 29 },
- { 9, 17, 60, 2, 34, 56, 20, 62, 39, 12, 49, 6, 29, 56, 34, 48, 0, 58, 22, 38, 18, 43, 56, 0, 63, 14, 55, 3, 59, 31, 15, 45, 0, 49, 6, 58, 3, 38, 12, 45, 0, 37, 29, 57, 13, 39, 30, 49, 0, 23, 44, 36, 16, 57, 13, 54, 11, 24, 63, 9, 53, 7, 62, 42, 0, 59, 15, 23, 63, 34, 40, 16, 32, 0, 53, 12, 48, 28, 59, 33, 0, 53, 9, 27, 3, 22, 54, 5, 56, 9, 61, 13, 42, 14, 52, 19, 0, 21, 47, 27, 53, 36, 3, 50, 39, 58, 25, 40, 53, 28, 12, 50, 0, 59, 32, 2, 21, 34, 26, 46, 37, 7, 18, 47, 24, 14, 53, 42 },
- { 61, 32, 13, 54, 29, 7, 46, 13, 28, 57, 18, 41, 53, 15, 9, 39, 24, 49, 33, 3, 53, 9, 26, 32, 40, 28, 46, 39, 25, 9, 56, 21, 63, 37, 26, 22, 51, 27, 17, 56, 31, 53, 4, 43, 22, 46, 12, 18, 60, 40, 20, 26, 50, 21, 39, 5, 49, 33, 16, 44, 22, 46, 20, 32, 24, 45, 8, 43, 12, 46, 4, 48, 56, 20, 29, 58, 3, 40, 10, 42, 31, 21, 47, 41, 56, 38, 15, 42, 36, 27, 20, 33, 55, 3, 26, 44, 31, 54, 12, 35, 9, 63, 28, 10, 21, 32, 9, 60, 17, 8, 43, 29, 40, 16, 36, 48, 60, 7, 57, 14, 62, 31, 42, 15, 36, 40, 20, 26 },
- { 0, 37, 47, 23, 41, 18, 32, 48, 1, 35, 8, 25, 4, 26, 63, 20, 54, 8, 16, 61, 35, 23, 51, 15, 58, 7, 12, 20, 50, 34, 42, 4, 38, 10, 32, 47, 8, 60, 41, 20, 9, 25, 50, 19, 62, 1, 37, 56, 28, 8, 53, 11, 3, 58, 34, 43, 19, 60, 38, 4, 58, 31, 3, 51, 11, 55, 38, 30, 21, 58, 19, 26, 9, 44, 36, 13, 46, 20, 62, 24, 13, 60, 5, 28, 12, 34, 7, 59, 0, 53, 45, 6, 38, 30, 50, 7, 62, 16, 41, 5, 46, 18, 55, 42, 51, 5, 45, 23, 34, 48, 19, 58, 5, 25, 54, 19, 13, 41, 28, 21, 0, 49, 10, 60, 4, 51, 9, 45 },
- { 19, 28, 6, 58, 10, 51, 4, 22, 55, 42, 60, 45, 34, 51, 42, 5, 30, 45, 27, 40, 13, 47, 4, 49, 21, 38, 60, 29, 2, 57, 17, 27, 52, 19, 61, 14, 30, 34, 2, 44, 63, 33, 11, 35, 16, 51, 25, 6, 14, 47, 31, 61, 37, 29, 18, 8, 52, 2, 28, 54, 13, 41, 15, 62, 35, 18, 2, 60, 6, 33, 41, 61, 31, 6, 56, 17, 34, 50, 6, 52, 44, 35, 16, 51, 59, 24, 48, 18, 31, 40, 16, 49, 21, 60, 17, 39, 10, 49, 32, 57, 24, 39, 1, 25, 18, 62, 37, 12, 56, 1, 37, 11, 52, 44, 9, 30, 47, 4, 51, 40, 55, 25, 34, 27, 56, 30, 32, 54 },
- { 63, 40, 49, 15, 43, 26, 63, 38, 16, 20, 30, 12, 57, 14, 19, 60, 36, 12, 59, 2, 57, 17, 42, 31, 1, 44, 16, 35, 47, 11, 32, 48, 13, 43, 1, 39, 51, 12, 57, 23, 6, 40, 53, 3, 55, 31, 39, 60, 35, 44, 5, 15, 45, 1, 62, 41, 26, 14, 47, 22, 36, 27, 50, 9, 26, 47, 52, 28, 54, 16, 1, 13, 51, 39, 23, 63, 1, 30, 15, 26, 2, 57, 19, 37, 1, 44, 21, 50, 13, 63, 8, 24, 56, 1, 35, 25, 58, 20, 2, 28, 14, 51, 33, 59, 13, 30, 4, 49, 31, 24, 63, 26, 33, 3, 58, 38, 62, 24, 32, 8, 17, 45, 5, 48, 18, 3, 43, 11 },
- { 21, 4, 24, 34, 59, 1, 37, 11, 53, 5, 47, 2, 22, 40, 32, 1, 24, 50, 21, 29, 38, 25, 63, 8, 55, 24, 53, 6, 62, 23, 59, 3, 54, 20, 58, 24, 5, 46, 15, 38, 48, 14, 27, 42, 23, 7, 46, 10, 17, 58, 25, 52, 23, 32, 49, 12, 55, 30, 40, 7, 59, 1, 56, 21, 39, 4, 23, 15, 37, 46, 55, 42, 21, 4, 48, 8, 45, 54, 37, 55, 32, 8, 46, 10, 30, 54, 4, 41, 25, 29, 36, 48, 11, 43, 14, 47, 5, 43, 53, 36, 61, 10, 45, 6, 41, 54, 27, 43, 16, 55, 6, 46, 18, 42, 23, 15, 1, 45, 12, 60, 37, 22, 62, 12, 39, 59, 16, 52 },
- { 47, 35, 56, 7, 19, 46, 31, 50, 33, 24, 61, 35, 50, 7, 53, 44, 55, 6, 46, 10, 52, 5, 21, 43, 36, 10, 18, 41, 26, 37, 8, 29, 40, 36, 9, 49, 34, 26, 61, 21, 7, 59, 18, 62, 29, 54, 20, 32, 51, 0, 40, 10, 55, 6, 20, 36, 9, 61, 5, 51, 44, 19, 33, 43, 13, 57, 40, 63, 8, 24, 29, 10, 60, 34, 27, 40, 25, 18, 10, 42, 21, 49, 26, 62, 38, 12, 33, 61, 5, 57, 2, 19, 54, 28, 62, 22, 38, 31, 16, 7, 22, 47, 29, 17, 35, 8, 20, 51, 2, 40, 22, 50, 13, 61, 28, 53, 35, 20, 56, 30, 2, 53, 14, 41, 23, 34, 8, 31 },
- { 12, 2, 42, 29, 52, 13, 21, 8, 55, 14, 41, 17, 28, 58, 23, 11, 17, 36, 31, 62, 17, 34, 50, 14, 28, 61, 33, 52, 2, 51, 17, 45, 7, 25, 62, 30, 18, 55, 0, 42, 30, 35, 45, 1, 12, 48, 3, 63, 21, 36, 30, 48, 19, 59, 43, 27, 46, 17, 34, 25, 12, 29, 53, 6, 48, 31, 11, 34, 49, 3, 36, 50, 19, 47, 14, 61, 11, 36, 58, 4, 60, 14, 39, 22, 6, 52, 15, 35, 17, 46, 31, 42, 9, 34, 3, 52, 12, 60, 26, 56, 40, 2, 53, 23, 57, 38, 62, 14, 36, 59, 10, 31, 39, 6, 49, 9, 41, 26, 5, 48, 43, 27, 33, 58, 1, 50, 25, 57 },
- { 61, 37, 15, 61, 3, 39, 58, 43, 26, 0, 44, 10, 47, 3, 37, 63, 28, 43, 13, 39, 3, 57, 30, 59, 0, 48, 5, 43, 13, 22, 60, 33, 55, 15, 42, 4, 52, 10, 45, 13, 54, 4, 24, 49, 37, 26, 41, 14, 42, 9, 61, 13, 38, 23, 3, 53, 0, 58, 21, 42, 63, 10, 17, 61, 25, 0, 58, 28, 17, 44, 57, 12, 27, 0, 55, 5, 52, 28, 23, 47, 29, 0, 43, 17, 58, 28, 47, 23, 55, 10, 58, 23, 51, 40, 18, 33, 45, 0, 49, 8, 32, 61, 19, 48, 0, 26, 7, 47, 29, 18, 44, 0, 56, 34, 20, 59, 15, 51, 37, 18, 10, 52, 7, 20, 46, 9, 38, 17 },
- { 6, 27, 48, 23, 45, 29, 5, 18, 38, 62, 27, 56, 20, 32, 15, 9, 48, 0, 54, 22, 45, 20, 7, 41, 23, 39, 19, 27, 58, 31, 44, 0, 12, 50, 23, 56, 20, 39, 32, 59, 16, 52, 33, 9, 57, 22, 6, 58, 28, 50, 24, 2, 56, 35, 16, 45, 32, 38, 15, 54, 2, 38, 46, 22, 35, 45, 20, 5, 52, 25, 7, 35, 59, 32, 22, 43, 38, 3, 51, 16, 34, 53, 32, 50, 3, 40, 8, 43, 0, 39, 27, 4, 14, 61, 8, 55, 15, 41, 20, 44, 27, 13, 39, 11, 46, 42, 54, 33, 4, 52, 23, 61, 14, 25, 43, 2, 33, 11, 63, 29, 61, 17, 40, 55, 22, 62, 28, 44 },
- { 20, 54, 8, 56, 35, 10, 63, 31, 52, 12, 48, 6, 59, 41, 52, 33, 19, 58, 25, 49, 11, 37, 47, 12, 54, 15, 56, 35, 7, 47, 16, 53, 28, 34, 5, 37, 28, 8, 48, 3, 28, 38, 18, 61, 16, 43, 53, 32, 4, 17, 47, 27, 44, 8, 63, 10, 25, 49, 6, 37, 24, 52, 32, 3, 50, 12, 41, 56, 38, 14, 62, 20, 40, 16, 53, 31, 18, 63, 41, 9, 59, 7, 13, 25, 57, 20, 63, 26, 53, 18, 48, 62, 30, 46, 21, 25, 58, 29, 36, 4, 55, 34, 6, 60, 31, 16, 21, 12, 58, 38, 9, 29, 47, 7, 52, 30, 57, 44, 22, 0, 35, 45, 3, 31, 14, 36, 0, 51 },
- { 42, 14, 33, 24, 16, 49, 40, 2, 22, 33, 16, 36, 25, 1, 21, 61, 38, 8, 33, 4, 62, 26, 29, 60, 6, 46, 30, 11, 63, 4, 36, 40, 19, 57, 46, 11, 41, 63, 22, 25, 58, 10, 46, 2, 34, 27, 11, 38, 56, 34, 12, 53, 18, 33, 41, 51, 13, 28, 60, 20, 47, 14, 29, 59, 16, 62, 8, 22, 32, 47, 9, 49, 2, 44, 7, 12, 45, 6, 20, 27, 45, 24, 62, 42, 36, 11, 33, 15, 37, 7, 32, 10, 37, 1, 35, 50, 6, 11, 63, 24, 52, 15, 50, 24, 3, 37, 56, 27, 34, 22, 49, 16, 36, 62, 17, 39, 4, 15, 54, 24, 50, 8, 58, 26, 49, 54, 11, 30 },
- { 4, 59, 41, 1, 53, 12, 25, 45, 59, 7, 51, 39, 54, 14, 46, 4, 27, 53, 16, 44, 18, 51, 1, 32, 25, 2, 50, 40, 20, 54, 24, 9, 62, 2, 27, 60, 1, 17, 36, 50, 6, 40, 30, 55, 41, 19, 49, 1, 21, 60, 40, 5, 62, 1, 22, 30, 57, 4, 43, 31, 1, 55, 40, 7, 27, 37, 30, 54, 1, 19, 42, 30, 56, 26, 62, 49, 24, 57, 37, 56, 2, 39, 16, 5, 30, 55, 3, 49, 60, 23, 56, 44, 17, 52, 13, 42, 28, 48, 18, 45, 9, 37, 21, 41, 58, 10, 48, 1, 63, 5, 41, 57, 2, 24, 12, 48, 27, 42, 32, 46, 13, 38, 19, 34, 5, 41, 25, 60 },
- { 39, 28, 21, 46, 32, 57, 36, 9, 19, 42, 4, 29, 11, 43, 30, 49, 13, 42, 35, 56, 9, 39, 15, 52, 36, 61, 18, 26, 45, 14, 31, 48, 21, 43, 14, 33, 49, 54, 14, 44, 21, 62, 13, 23, 8, 62, 15, 51, 44, 7, 30, 37, 20, 42, 56, 7, 39, 18, 50, 11, 61, 9, 19, 43, 57, 2, 48, 11, 39, 60, 28, 4, 37, 17, 35, 1, 33, 11, 31, 14, 48, 19, 35, 51, 46, 21, 44, 29, 12, 41, 2, 22, 58, 26, 54, 4, 59, 38, 2, 33, 57, 1, 63, 13, 28, 51, 15, 40, 18, 45, 8, 30, 43, 37, 54, 19, 8, 59, 21, 6, 60, 29, 55, 10, 63, 15, 47, 17 },
- { 3, 50, 10, 62, 18, 5, 27, 49, 60, 23, 55, 18, 62, 24, 56, 10, 59, 28, 2, 23, 34, 59, 43, 20, 10, 42, 8, 49, 1, 37, 57, 6, 51, 29, 53, 7, 23, 31, 5, 32, 51, 0, 35, 54, 45, 31, 5, 26, 36, 24, 55, 15, 48, 29, 14, 48, 26, 60, 21, 41, 36, 26, 50, 33, 14, 44, 17, 24, 52, 15, 46, 23, 54, 6, 47, 21, 60, 50, 4, 53, 29, 61, 8, 23, 1, 60, 19, 6, 53, 16, 47, 34, 6, 39, 16, 31, 12, 20, 53, 22, 30, 43, 25, 46, 35, 6, 44, 32, 53, 26, 55, 19, 11, 59, 5, 33, 51, 1, 35, 53, 25, 3, 42, 23, 44, 32, 7, 53 },
- { 22, 44, 37, 6, 26, 51, 38, 0, 34, 13, 31, 46, 3, 37, 6, 19, 40, 21, 47, 63, 12, 5, 29, 55, 22, 58, 34, 28, 60, 22, 11, 41, 17, 38, 9, 44, 59, 39, 56, 19, 11, 47, 25, 15, 3, 39, 57, 17, 61, 11, 46, 3, 58, 9, 54, 35, 2, 34, 8, 45, 15, 56, 5, 23, 53, 33, 63, 35, 4, 59, 10, 51, 13, 61, 29, 41, 15, 25, 43, 19, 40, 10, 54, 33, 41, 12, 38, 51, 31, 26, 61, 9, 30, 45, 24, 62, 49, 40, 10, 61, 14, 49, 5, 17, 54, 20, 60, 23, 3, 13, 35, 50, 32, 23, 46, 27, 38, 63, 16, 12, 39, 48, 18, 51, 1, 27, 56, 35 },
- { 63, 15, 30, 55, 43, 14, 57, 17, 53, 44, 7, 48, 26, 50, 32, 60, 0, 53, 14, 31, 50, 24, 46, 0, 38, 13, 4, 52, 16, 45, 30, 59, 0, 25, 55, 35, 16, 10, 26, 42, 58, 29, 60, 38, 50, 22, 28, 47, 0, 50, 28, 19, 33, 39, 11, 44, 16, 52, 24, 59, 3, 38, 27, 51, 0, 21, 7, 42, 26, 34, 21, 40, 33, 18, 39, 3, 54, 38, 8, 59, 0, 44, 27, 15, 58, 28, 57, 9, 43, 0, 36, 50, 20, 59, 8, 34, 0, 27, 47, 7, 36, 19, 56, 32, 0, 38, 11, 29, 62, 47, 6, 61, 0, 41, 14, 56, 10, 23, 45, 31, 57, 8, 36, 13, 58, 38, 11, 19 },
- { 0, 34, 12, 47, 21, 2, 40, 30, 11, 25, 61, 20, 40, 15, 35, 22, 45, 36, 7, 41, 17, 57, 9, 48, 32, 62, 44, 24, 35, 3, 54, 13, 33, 63, 19, 4, 48, 22, 62, 2, 37, 8, 33, 6, 20, 52, 9, 32, 43, 13, 39, 63, 25, 4, 49, 23, 62, 32, 9, 30, 48, 18, 63, 12, 46, 29, 58, 13, 48, 8, 57, 31, 0, 51, 9, 58, 12, 22, 47, 29, 35, 22, 49, 5, 46, 4, 34, 20, 63, 24, 56, 11, 41, 3, 51, 19, 56, 35, 17, 58, 28, 42, 9, 45, 59, 26, 51, 42, 17, 36, 25, 15, 53, 21, 44, 3, 30, 55, 5, 50, 21, 28, 61, 32, 6, 49, 28, 46 },
- { 58, 42, 60, 4, 31, 59, 22, 63, 35, 38, 9, 54, 1, 57, 8, 51, 16, 58, 27, 53, 3, 38, 30, 15, 27, 6, 19, 56, 10, 50, 21, 36, 47, 5, 43, 28, 51, 32, 13, 46, 18, 54, 16, 43, 63, 12, 36, 59, 22, 34, 5, 52, 17, 59, 27, 41, 0, 19, 55, 37, 13, 43, 6, 34, 41, 10, 36, 55, 19, 44, 3, 16, 58, 27, 49, 25, 32, 62, 17, 55, 13, 63, 18, 52, 25, 37, 17, 48, 13, 32, 5, 46, 28, 37, 14, 43, 25, 5, 51, 39, 3, 52, 33, 22, 8, 40, 12, 4, 57, 9, 46, 39, 28, 58, 13, 62, 17, 42, 19, 36, 0, 47, 16, 43, 24, 21, 54, 13 },
- { 25, 9, 23, 50, 36, 8, 45, 14, 3, 51, 16, 28, 44, 12, 42, 29, 4, 26, 10, 47, 22, 61, 18, 54, 51, 39, 46, 13, 41, 26, 58, 7, 18, 39, 12, 57, 15, 1, 52, 27, 41, 23, 48, 1, 27, 45, 18, 2, 57, 26, 55, 8, 43, 31, 6, 58, 14, 51, 40, 5, 61, 31, 24, 54, 17, 60, 22, 1, 39, 30, 53, 45, 36, 13, 43, 5, 45, 2, 37, 6, 34, 42, 2, 39, 10, 62, 7, 54, 40, 18, 60, 15, 52, 21, 63, 8, 55, 46, 15, 30, 23, 13, 62, 16, 50, 24, 58, 31, 48, 21, 34, 2, 49, 7, 31, 37, 26, 48, 9, 61, 40, 11, 52, 2, 60, 40, 4, 37 },
- { 52, 28, 39, 16, 54, 19, 29, 55, 42, 20, 58, 33, 24, 63, 18, 55, 39, 62, 43, 34, 12, 40, 6, 35, 2, 25, 8, 62, 34, 1, 31, 42, 61, 27, 53, 24, 40, 61, 34, 8, 59, 4, 30, 56, 40, 6, 53, 42, 10, 48, 16, 37, 12, 46, 21, 36, 47, 11, 28, 45, 22, 10, 57, 2, 49, 31, 14, 44, 61, 11, 25, 6, 23, 63, 18, 36, 28, 56, 20, 51, 11, 48, 27, 56, 32, 22, 45, 30, 2, 42, 27, 39, 1, 44, 23, 31, 38, 22, 11, 61, 43, 54, 4, 47, 35, 2, 44, 16, 28, 54, 12, 62, 18, 43, 10, 52, 1, 58, 33, 15, 29, 56, 20, 34, 9, 30, 48, 17 },
- { 46, 2, 56, 11, 41, 1, 49, 6, 27, 47, 2, 48, 5, 32, 37, 3, 13, 19, 32, 1, 55, 28, 60, 17, 43, 59, 32, 20, 49, 16, 55, 23, 14, 46, 2, 36, 6, 30, 20, 49, 12, 47, 35, 14, 21, 60, 29, 14, 35, 24, 46, 1, 56, 29, 53, 8, 33, 23, 56, 1, 35, 46, 20, 39, 26, 4, 53, 28, 17, 38, 60, 34, 48, 9, 55, 15, 46, 7, 41, 31, 60, 24, 16, 36, 1, 59, 19, 52, 35, 6, 55, 11, 59, 33, 7, 57, 4, 29, 48, 1, 19, 26, 37, 30, 18, 63, 37, 6, 59, 1, 40, 24, 56, 33, 46, 22, 35, 7, 24, 53, 39, 5, 26, 45, 55, 18, 62, 7 },
- { 20, 60, 29, 34, 20, 62, 33, 52, 10, 36, 13, 60, 41, 21, 50, 27, 56, 49, 8, 51, 21, 45, 11, 48, 8, 23, 53, 3, 29, 44, 5, 52, 9, 32, 50, 17, 43, 56, 3, 38, 24, 10, 62, 25, 51, 9, 33, 49, 61, 7, 30, 62, 22, 19, 2, 42, 63, 5, 49, 18, 60, 15, 52, 7, 43, 56, 23, 50, 5, 50, 2, 20, 41, 30, 1, 52, 22, 61, 14, 26, 3, 43, 53, 7, 47, 28, 11, 14, 23, 58, 33, 25, 47, 13, 50, 17, 40, 54, 34, 60, 41, 6, 59, 14, 50, 7, 25, 55, 20, 42, 51, 8, 27, 4, 16, 60, 28, 50, 44, 3, 22, 49, 63, 12, 33, 1, 43, 31 },
- { 36, 5, 46, 8, 44, 24, 13, 39, 25, 57, 31, 18, 8, 52, 10, 45, 6, 30, 36, 24, 63, 4, 33, 26, 57, 40, 15, 56, 37, 12, 40, 25, 37, 58, 11, 63, 21, 45, 16, 60, 31, 53, 18, 33, 3, 45, 23, 0, 20, 54, 40, 15, 50, 38, 60, 16, 25, 42, 29, 38, 7, 41, 25, 62, 18, 33, 8, 35, 42, 16, 32, 56, 12, 39, 59, 19, 34, 9, 49, 38, 57, 12, 21, 50, 14, 40, 61, 44, 50, 9, 49, 19, 3, 29, 35, 62, 12, 24, 7, 18, 52, 32, 10, 46, 21, 41, 32, 11, 36, 29, 14, 34, 60, 38, 54, 11, 41, 14, 19, 57, 32, 16, 7, 41, 51, 25, 14, 57 },
- { 53, 18, 26, 50, 15, 58, 4, 63, 17, 43, 7, 40, 61, 35, 15, 41, 23, 60, 16, 38, 14, 42, 19, 50, 0, 31, 10, 46, 27, 63, 18, 60, 0, 20, 29, 39, 8, 26, 37, 5, 42, 0, 44, 39, 57, 17, 58, 41, 28, 37, 4, 32, 9, 44, 12, 31, 54, 10, 59, 14, 27, 53, 12, 36, 0, 47, 13, 63, 21, 58, 10, 24, 50, 27, 4, 26, 44, 53, 31, 0, 18, 42, 29, 33, 57, 4, 32, 26, 0, 38, 16, 61, 41, 53, 20, 0, 42, 44, 49, 27, 10, 56, 39, 0, 57, 15, 53, 49, 3, 61, 22, 47, 17, 5, 49, 26, 2, 63, 39, 10, 47, 27, 37, 23, 4, 59, 38, 10 },
- { 23, 39, 61, 3, 37, 28, 48, 31, 0, 34, 51, 23, 2, 26, 58, 0, 53, 11, 46, 1, 57, 29, 52, 14, 37, 61, 21, 35, 2, 49, 7, 34, 47, 55, 4, 33, 54, 13, 58, 52, 19, 50, 22, 7, 13, 29, 36, 11, 51, 17, 60, 25, 55, 4, 34, 51, 0, 35, 20, 48, 32, 3, 51, 30, 59, 28, 40, 3, 46, 29, 54, 43, 7, 62, 47, 11, 39, 4, 23, 46, 55, 8, 63, 5, 25, 37, 18, 46, 21, 56, 31, 5, 36, 8, 45, 58, 26, 15, 2, 36, 47, 21, 29, 44, 25, 34, 3, 27, 43, 10, 52, 0, 45, 30, 24, 36, 43, 18, 34, 59, 0, 52, 61, 15, 44, 19, 30, 49 },
- { 0, 27, 12, 43, 54, 9, 22, 53, 21, 46, 15, 55, 29, 47, 20, 33, 39, 28, 59, 35, 9, 44, 5, 24, 47, 7, 52, 17, 56, 22, 30, 42, 14, 26, 45, 18, 49, 1, 24, 34, 11, 27, 55, 32, 61, 47, 2, 56, 6, 44, 13, 47, 36, 27, 58, 22, 16, 47, 40, 4, 57, 38, 21, 45, 16, 9, 56, 26, 11, 38, 0, 22, 36, 17, 33, 57, 16, 30, 62, 15, 35, 40, 20, 45, 59, 10, 54, 8, 63, 13, 52, 27, 22, 57, 28, 12, 32, 51, 55, 22, 63, 4, 16, 54, 12, 62, 45, 19, 58, 13, 32, 40, 20, 56, 7, 57, 9, 54, 6, 29, 42, 21, 8, 55, 35, 47, 6, 41 },
- { 56, 33, 58, 32, 19, 35, 42, 6, 59, 11, 38, 5, 49, 12, 62, 7, 52, 17, 5, 25, 54, 20, 61, 31, 54, 27, 41, 11, 44, 5, 59, 12, 36, 51, 10, 61, 28, 41, 48, 9, 43, 63, 5, 40, 20, 8, 49, 26, 34, 21, 58, 1, 18, 45, 7, 39, 61, 26, 8, 50, 23, 10, 63, 5, 55, 37, 19, 49, 52, 15, 59, 47, 13, 54, 1, 25, 42, 58, 10, 48, 3, 27, 50, 1, 17, 48, 34, 41, 16, 40, 2, 45, 10, 39, 17, 61, 5, 38, 19, 9, 41, 31, 60, 38, 5, 23, 36, 8, 30, 55, 24, 63, 12, 48, 14, 51, 31, 20, 45, 25, 12, 50, 32, 2, 28, 11, 62, 14 },
- { 44, 16, 7, 48, 1, 62, 16, 50, 27, 33, 61, 25, 17, 44, 31, 14, 22, 43, 32, 48, 18, 40, 8, 36, 3, 16, 33, 62, 23, 38, 25, 53, 2, 21, 41, 6, 22, 15, 59, 29, 16, 37, 26, 15, 52, 42, 23, 15, 54, 39, 10, 30, 53, 11, 49, 24, 2, 43, 55, 17, 34, 44, 15, 31, 24, 44, 2, 32, 7, 35, 25, 5, 40, 45, 29, 51, 6, 21, 37, 52, 24, 60, 13, 31, 53, 23, 2, 28, 49, 24, 31, 60, 20, 51, 1, 34, 48, 14, 59, 33, 50, 1, 18, 33, 48, 60, 17, 51, 39, 6, 38, 2, 35, 29, 40, 23, 1, 62, 15, 53, 37, 17, 46, 57, 40, 51, 24, 22 },
- { 5, 37, 52, 24, 45, 13, 40, 3, 45, 9, 19, 42, 56, 4, 37, 46, 56, 2, 63, 11, 51, 1, 49, 13, 59, 45, 39, 1, 48, 15, 58, 9, 46, 31, 54, 35, 57, 38, 3, 46, 56, 4, 47, 57, 1, 30, 38, 63, 3, 46, 28, 63, 41, 14, 33, 62, 19, 32, 13, 28, 61, 1, 53, 42, 11, 60, 22, 62, 27, 42, 61, 31, 19, 8, 61, 12, 32, 55, 2, 18, 33, 12, 43, 36, 9, 62, 30, 55, 6, 58, 35, 7, 43, 29, 54, 23, 43, 30, 3, 25, 11, 45, 52, 28, 7, 14, 42, 1, 22, 50, 16, 53, 19, 59, 4, 46, 33, 41, 4, 35, 58, 5, 26, 13, 20, 2, 34, 54 },
- { 30, 63, 21, 10, 26, 55, 29, 59, 23, 39, 53, 1, 36, 24, 59, 27, 10, 34, 23, 38, 30, 60, 22, 42, 28, 19, 9, 57, 30, 19, 43, 33, 13, 63, 3, 19, 11, 50, 31, 20, 14, 34, 10, 35, 17, 59, 7, 31, 19, 25, 50, 5, 20, 57, 29, 6, 52, 41, 4, 46, 20, 37, 26, 17, 49, 6, 39, 18, 53, 14, 3, 49, 57, 23, 34, 48, 14, 41, 28, 38, 56, 6, 58, 25, 39, 19, 43, 15, 37, 11, 47, 18, 53, 4, 37, 9, 62, 21, 53, 40, 57, 24, 13, 40, 56, 26, 47, 31, 59, 25, 45, 27, 10, 43, 21, 61, 13, 27, 48, 9, 23, 43, 31, 62, 38, 59, 9, 47 },
- { 25, 4, 40, 60, 34, 6, 18, 36, 8, 57, 12, 30, 49, 14, 6, 54, 41, 16, 50, 6, 43, 15, 34, 4, 53, 24, 50, 35, 4, 51, 7, 55, 28, 24, 39, 44, 60, 7, 25, 62, 42, 53, 24, 61, 28, 45, 52, 12, 48, 37, 9, 35, 43, 3, 37, 48, 12, 58, 30, 52, 9, 59, 6, 57, 33, 29, 48, 4, 37, 45, 20, 34, 10, 39, 0, 60, 22, 45, 8, 63, 21, 42, 14, 49, 3, 56, 11, 46, 21, 61, 0, 42, 25, 13, 63, 17, 36, 8, 46, 16, 6, 35, 63, 0, 21, 37, 4, 57, 9, 34, 5, 61, 48, 32, 8, 37, 54, 17, 56, 30, 60, 0, 50, 16, 7, 29, 42, 17 },
- { 32, 50, 15, 48, 2, 43, 52, 25, 47, 16, 32, 63, 21, 52, 40, 19, 0, 61, 29, 58, 20, 56, 26, 46, 12, 55, 6, 22, 62, 32, 17, 40, 0, 49, 34, 8, 27, 32, 48, 0, 21, 39, 5, 44, 12, 6, 22, 40, 0, 57, 16, 60, 23, 17, 54, 22, 36, 15, 24, 39, 19, 34, 47, 23, 0, 54, 13, 51, 24, 9, 55, 16, 52, 27, 44, 20, 4, 54, 26, 49, 0, 30, 46, 16, 29, 51, 34, 4, 52, 28, 33, 15, 57, 39, 26, 49, 0, 56, 27, 31, 48, 20, 43, 29, 53, 11, 46, 19, 41, 13, 55, 18, 0, 57, 26, 51, 2, 44, 6, 38, 14, 40, 22, 45, 36, 53, 3, 57 },
- { 44, 12, 37, 28, 22, 57, 11, 38, 0, 51, 9, 41, 4, 29, 11, 47, 33, 45, 12, 26, 3, 36, 9, 63, 31, 16, 38, 44, 14, 47, 25, 61, 20, 58, 15, 47, 17, 57, 13, 36, 9, 51, 18, 29, 50, 36, 54, 20, 61, 27, 32, 13, 53, 44, 9, 27, 0, 63, 45, 2, 56, 10, 14, 43, 41, 28, 58, 11, 35, 60, 30, 41, 6, 63, 11, 51, 37, 32, 15, 10, 35, 53, 5, 61, 22, 7, 26, 59, 23, 9, 44, 48, 21, 3, 51, 32, 24, 41, 12, 61, 2, 55, 9, 15, 35, 58, 28, 15, 62, 30, 37, 23, 42, 29, 11, 17, 35, 24, 63, 20, 52, 28, 8, 55, 11, 23, 47, 19 },
- { 0, 56, 8, 53, 14, 31, 61, 20, 55, 28, 62, 18, 35, 60, 25, 57, 7, 23, 39, 54, 47, 17, 43, 0, 40, 59, 29, 2, 56, 10, 37, 5, 43, 11, 29, 52, 1, 23, 54, 41, 59, 30, 55, 1, 62, 15, 33, 4, 43, 10, 47, 39, 1, 31, 40, 60, 49, 33, 7, 55, 26, 50, 31, 61, 8, 18, 21, 32, 44, 1, 25, 47, 18, 36, 30, 23, 59, 7, 40, 59, 27, 19, 38, 32, 44, 54, 40, 17, 38, 60, 27, 6, 35, 55, 10, 14, 44, 5, 50, 17, 38, 26, 42, 50, 18, 3, 44, 52, 2, 49, 7, 52, 15, 46, 62, 39, 55, 10, 31, 48, 3, 58, 33, 18, 61, 34, 13, 59 },
- { 39, 27, 63, 20, 35, 41, 4, 45, 26, 5, 38, 13, 44, 2, 50, 17, 37, 52, 2, 13, 28, 58, 24, 51, 21, 8, 34, 48, 27, 42, 18, 51, 31, 56, 5, 36, 38, 44, 4, 17, 26, 11, 38, 23, 42, 8, 56, 39, 24, 51, 5, 56, 21, 59, 14, 6, 18, 42, 22, 35, 16, 37, 3, 25, 39, 46, 63, 5, 50, 17, 58, 8, 55, 3, 50, 12, 43, 17, 47, 2, 51, 9, 62, 12, 1, 35, 13, 50, 1, 37, 12, 51, 19, 29, 46, 59, 22, 58, 33, 45, 22, 60, 10, 32, 61, 39, 8, 33, 25, 36, 20, 60, 38, 4, 21, 5, 28, 45, 12, 18, 42, 11, 49, 1, 27, 40, 6, 30 },
- { 24, 16, 42, 1, 50, 10, 48, 17, 33, 43, 24, 48, 21, 55, 31, 42, 10, 21, 63, 35, 49, 6, 33, 13, 41, 53, 10, 20, 60, 6, 53, 26, 12, 41, 22, 60, 14, 28, 63, 33, 49, 3, 45, 16, 48, 26, 14, 46, 18, 30, 35, 26, 8, 50, 29, 51, 25, 57, 12, 47, 53, 9, 62, 20, 54, 2, 36, 15, 40, 28, 33, 13, 38, 24, 46, 1, 29, 56, 33, 20, 44, 24, 41, 26, 57, 20, 63, 8, 30, 55, 5, 41, 62, 8, 34, 2, 37, 10, 19, 6, 37, 1, 53, 23, 5, 27, 58, 22, 43, 12, 50, 26, 9, 34, 54, 32, 49, 1, 59, 37, 22, 46, 25, 36, 51, 15, 54, 46 },
- { 52, 7, 45, 33, 26, 58, 14, 60, 7, 54, 3, 58, 8, 34, 14, 5, 59, 30, 18, 44, 8, 22, 48, 62, 3, 26, 55, 38, 23, 16, 39, 1, 62, 24, 49, 9, 53, 19, 46, 7, 19, 60, 31, 58, 2, 34, 53, 7, 59, 2, 62, 42, 46, 19, 36, 11, 44, 4, 38, 28, 1, 43, 32, 51, 12, 29, 56, 22, 52, 2, 62, 49, 22, 60, 14, 35, 63, 5, 25, 57, 14, 53, 4, 46, 18, 31, 42, 22, 47, 20, 58, 31, 16, 43, 23, 54, 30, 42, 52, 57, 29, 49, 30, 13, 45, 48, 16, 55, 6, 63, 1, 44, 14, 58, 19, 47, 15, 24, 51, 34, 6, 55, 5, 63, 20, 41, 21, 9 },
- { 30, 62, 18, 55, 5, 23, 39, 29, 49, 30, 15, 36, 28, 46, 60, 25, 39, 46, 4, 32, 61, 40, 15, 30, 36, 45, 14, 2, 49, 33, 57, 45, 18, 32, 3, 45, 30, 2, 35, 52, 40, 27, 13, 21, 38, 63, 20, 28, 37, 23, 16, 10, 13, 55, 2, 62, 21, 32, 60, 17, 58, 23, 5, 40, 16, 48, 7, 45, 10, 26, 43, 19, 6, 31, 52, 21, 39, 16, 48, 9, 37, 28, 36, 55, 7, 48, 3, 59, 15, 45, 25, 1, 53, 13, 47, 7, 62, 15, 4, 25, 12, 41, 18, 60, 38, 11, 34, 19, 39, 31, 29, 56, 23, 42, 3, 27, 60, 41, 8, 16, 61, 29, 43, 9, 32, 2, 60, 34 },
- { 3, 38, 13, 37, 52, 44, 2, 19, 12, 42, 63, 19, 40, 1, 20, 50, 12, 55, 15, 56, 27, 1, 54, 11, 57, 18, 32, 63, 44, 4, 29, 13, 37, 61, 35, 16, 42, 57, 12, 22, 6, 55, 43, 10, 50, 5, 44, 11, 48, 52, 34, 58, 28, 41, 38, 30, 7, 52, 11, 49, 30, 14, 45, 27, 59, 34, 21, 38, 32, 58, 11, 36, 56, 42, 9, 41, 3, 54, 31, 42, 0, 60, 16, 11, 39, 24, 52, 33, 6, 36, 10, 40, 32, 60, 26, 20, 39, 28, 47, 34, 63, 8, 54, 3, 24, 56, 0, 51, 13, 47, 16, 40, 7, 35, 52, 11, 36, 4, 57, 30, 39, 13, 18, 50, 58, 28, 12, 48 },
- { 57, 24, 49, 21, 10, 31, 61, 36, 56, 0, 22, 53, 11, 56, 32, 7, 36, 27, 41, 9, 46, 19, 34, 42, 25, 7, 50, 9, 28, 21, 54, 8, 50, 7, 27, 59, 10, 25, 48, 62, 37, 0, 33, 58, 25, 18, 32, 61, 0, 15, 45, 5, 50, 3, 23, 55, 47, 17, 40, 6, 60, 34, 53, 8, 41, 0, 61, 13, 54, 4, 46, 28, 0, 17, 48, 27, 58, 13, 23, 61, 33, 21, 50, 30, 62, 8, 14, 29, 56, 27, 61, 49, 17, 2, 44, 11, 51, 0, 59, 17, 40, 20, 32, 47, 36, 21, 42, 28, 60, 4, 54, 10, 59, 17, 30, 62, 21, 43, 26, 48, 0, 56, 36, 25, 8, 44, 39, 17 },
- { 10, 42, 4, 59, 27, 47, 8, 23, 51, 32, 45, 6, 37, 26, 48, 43, 62, 0, 21, 53, 38, 12, 51, 5, 60, 47, 24, 37, 59, 15, 35, 47, 22, 55, 0, 50, 21, 40, 6, 29, 15, 52, 24, 8, 41, 55, 13, 29, 40, 56, 24, 31, 19, 33, 61, 15, 0, 35, 24, 42, 21, 2, 19, 57, 24, 15, 30, 50, 20, 25, 40, 16, 57, 34, 61, 8, 29, 45, 6, 49, 11, 47, 2, 44, 19, 57, 38, 50, 12, 42, 21, 4, 35, 52, 28, 56, 23, 36, 13, 45, 4, 52, 27, 14, 6, 62, 9, 45, 21, 37, 25, 46, 33, 49, 0, 44, 7, 53, 13, 19, 53, 31, 3, 47, 15, 56, 22, 51 },
- { 35, 28, 53, 32, 1, 16, 54, 40, 9, 17, 25, 58, 14, 59, 3, 22, 16, 51, 31, 5, 23, 58, 28, 17, 35, 20, 0, 42, 11, 52, 3, 31, 41, 17, 43, 13, 32, 54, 18, 60, 32, 45, 17, 49, 2, 36, 51, 22, 7, 36, 9, 63, 48, 12, 46, 26, 43, 28, 63, 13, 48, 37, 51, 33, 5, 47, 55, 9, 42, 63, 7, 51, 24, 12, 37, 19, 55, 34, 18, 38, 15, 28, 54, 34, 5, 43, 22, 0, 48, 14, 54, 24, 58, 9, 38, 5, 32, 55, 21, 30, 49, 9, 59, 43, 30, 51, 35, 26, 7, 53, 2, 22, 14, 27, 57, 18, 38, 24, 33, 45, 10, 41, 20, 60, 37, 5, 32, 0 },
- { 63, 19, 15, 40, 62, 35, 14, 28, 46, 61, 4, 49, 35, 10, 29, 54, 33, 8, 45, 62, 37, 1, 43, 55, 10, 52, 61, 30, 19, 40, 25, 62, 11, 38, 27, 58, 36, 3, 46, 8, 39, 4, 62, 28, 47, 20, 4, 54, 47, 27, 43, 1, 21, 38, 8, 58, 10, 54, 4, 56, 9, 26, 12, 39, 60, 27, 18, 37, 1, 31, 35, 5, 45, 50, 2, 43, 26, 1, 59, 23, 56, 40, 7, 26, 58, 17, 32, 63, 25, 39, 7, 31, 45, 19, 63, 15, 48, 8, 37, 61, 16, 34, 1, 56, 18, 3, 15, 58, 49, 32, 63, 41, 55, 5, 40, 22, 50, 6, 59, 2, 63, 23, 52, 11, 26, 61, 44, 23 },
- { 11, 56, 46, 6, 22, 43, 58, 3, 34, 21, 38, 30, 18, 44, 52, 13, 41, 57, 17, 28, 14, 49, 25, 7, 33, 39, 26, 6, 56, 48, 1, 20, 56, 5, 46, 9, 19, 51, 30, 25, 56, 21, 35, 14, 57, 42, 16, 33, 10, 57, 17, 59, 41, 25, 53, 37, 20, 40, 30, 18, 31, 62, 44, 22, 3, 44, 11, 48, 23, 53, 18, 60, 29, 22, 62, 15, 53, 47, 10, 41, 3, 19, 52, 36, 13, 46, 10, 35, 3, 61, 41, 16, 1, 50, 26, 42, 18, 46, 2, 25, 54, 20, 39, 23, 47, 31, 41, 12, 38, 17, 8, 19, 31, 48, 12, 61, 9, 54, 29, 35, 15, 38, 6, 43, 34, 14, 7, 47 },
- { 39, 2, 33, 26, 53, 8, 18, 50, 41, 12, 53, 1, 63, 24, 19, 39, 2, 24, 47, 10, 60, 38, 19, 63, 48, 4, 15, 45, 32, 14, 60, 36, 29, 53, 23, 63, 34, 12, 61, 1, 43, 11, 53, 30, 1, 26, 60, 45, 23, 39, 3, 29, 12, 50, 4, 16, 51, 3, 45, 36, 50, 1, 16, 54, 35, 14, 57, 30, 58, 9, 46, 14, 41, 10, 32, 38, 4, 30, 21, 51, 32, 63, 25, 1, 60, 27, 53, 18, 51, 22, 28, 55, 34, 12, 40, 3, 60, 29, 57, 41, 6, 44, 11, 53, 8, 61, 24, 57, 1, 28, 44, 59, 36, 3, 34, 25, 41, 31, 16, 44, 22, 47, 28, 58, 1, 49, 54, 29 },
- { 58, 25, 50, 13, 38, 30, 60, 24, 6, 57, 27, 42, 9, 45, 6, 61, 30, 50, 4, 34, 29, 3, 46, 13, 22, 42, 58, 28, 9, 39, 23, 44, 7, 15, 44, 2, 40, 15, 47, 41, 23, 37, 7, 59, 38, 11, 34, 6, 62, 14, 52, 35, 55, 19, 32, 61, 33, 24, 57, 6, 22, 59, 29, 7, 49, 25, 40, 3, 17, 39, 27, 52, 0, 55, 16, 57, 24, 61, 36, 6, 29, 12, 48, 39, 20, 44, 6, 40, 33, 5, 48, 10, 57, 36, 22, 51, 33, 9, 24, 12, 62, 29, 50, 35, 14, 43, 5, 33, 47, 52, 13, 23, 10, 51, 56, 16, 46, 1, 49, 4, 61, 9, 52, 18, 31, 21, 36, 17 },
- { 19, 42, 9, 48, 2, 44, 11, 37, 48, 20, 33, 16, 55, 35, 49, 15, 37, 20, 59, 16, 53, 22, 56, 31, 50, 11, 34, 54, 16, 51, 4, 49, 33, 53, 21, 28, 56, 24, 31, 9, 52, 16, 48, 24, 44, 13, 51, 20, 31, 49, 18, 6, 34, 2, 44, 14, 47, 8, 15, 43, 13, 41, 33, 52, 20, 61, 7, 51, 34, 62, 4, 20, 36, 33, 43, 8, 46, 13, 53, 17, 45, 42, 9, 31, 52, 11, 30, 56, 13, 59, 17, 44, 27, 6, 62, 11, 43, 17, 49, 38, 26, 2, 16, 27, 58, 21, 54, 18, 26, 5, 35, 61, 43, 27, 7, 39, 14, 58, 37, 55, 20, 33, 13, 40, 62, 10, 55, 5 },
- { 51, 14, 61, 29, 59, 20, 55, 31, 0, 49, 11, 60, 3, 26, 22, 56, 0, 40, 12, 43, 41, 8, 36, 0, 17, 57, 24, 2, 46, 26, 61, 18, 0, 38, 12, 59, 6, 49, 3, 57, 19, 63, 5, 33, 18, 54, 28, 56, 0, 43, 26, 46, 63, 27, 56, 22, 27, 54, 38, 28, 63, 24, 10, 45, 0, 31, 42, 21, 12, 25, 44, 49, 59, 6, 26, 50, 3, 34, 27, 59, 0, 35, 62, 16, 4, 58, 47, 0, 43, 24, 37, 2, 54, 20, 46, 31, 0, 56, 34, 5, 55, 45, 60, 37, 0, 40, 10, 38, 63, 46, 15, 20, 0, 53, 21, 62, 30, 11, 24, 27, 40, 0, 57, 26, 3, 45, 27, 35 },
- };
-
- typedef struct _Color Color;
- typedef struct _QuantizeObj QuantizeObj;
- typedef void (* Pass1_Func) (QuantizeObj *);
- typedef void (* Pass2i_Func) (QuantizeObj *);
- typedef void (* Pass2_Func) (QuantizeObj *, Layer *, TileManager *);
- typedef void (* Cleanup_Func) (QuantizeObj *);
- typedef unsigned long ColorFreq;
- typedef ColorFreq *CFHistogram;
-
- struct _Color
- {
- int red;
- int green;
- int blue;
- };
-
- struct _QuantizeObj
- {
- Pass1_Func first_pass; /* first pass over image data creates colormap */
- Pass2i_Func second_pass_init; /* Initialize data which persists over invocations */
- Pass2_Func second_pass; /* second pass maps from image data to colormap */
- Cleanup_Func delete_func; /* function to clean up data associated with private */
-
- int desired_number_of_colors; /* Number of colors we will allow */
- int actual_number_of_colors; /* Number of colors actually needed */
- Color cmap[256]; /* colormap created by quantization */
- gulong index_used_count[256]; /* how many times an index was used */
- CFHistogram histogram; /* holds the histogram */
-
- int want_alpha_dither;
- int error_freedom; /* 0=much bleed, 1=controlled bleed */
- };
-
- typedef struct
- {
- /* The bounds of the box (inclusive); expressed as histogram indexes */
- int Rmin, Rmax;
- int Rhalferror;
- int Gmin, Gmax;
- int Ghalferror;
- int Bmin, Bmax;
- int Bhalferror;
-
- /* The volume (actually 2-norm) of the box */
- int volume;
-
- /* The number of nonzero histogram cells within this box */
- long colorcount;
-
- /* The sum of the weighted error within this box */
- guint64 error;
- /* The sum of the unweighted error within this box */
- guint64 rerror;
- guint64 gerror;
- guint64 berror;
-
- } box, *boxptr;
-
- typedef struct
- {
- long ncolors;
- long dither;
- } Options;
-
- typedef struct
- {
- GtkWidget* shell;
- GtkWidget* custom_palette_button;
- GimpImage* gimage;
- PaletteSelect* palette_select;
- int nodither_flag;
- int fsdither_flag;
- int fslowbleeddither_flag;
- int fixeddither_flag;
- int alphadither; /* flag */
- int remdups; /* flag */
- int num_cols;
- int palette;
- int makepal_flag;
- int webpal_flag;
- int custompal_flag;
- int monopal_flag;
- int reusepal_flag;
- } IndexedDialog;
-
- static void indexed_ok_callback (GtkWidget *, gpointer);
- static void indexed_cancel_callback (GtkWidget *, gpointer);
-
- static void indexed_custom_palette_button_callback (GtkWidget *widget, gpointer data);
- static void indexed_palette_select_destroy_callback (GtkWidget *widget, gpointer data);
-
- static void rgb_converter (Layer *, TileManager *, int);
- static void grayscale_converter (Layer *, TileManager *, int);
-
- static void zero_histogram_gray (CFHistogram);
- static void zero_histogram_rgb (CFHistogram);
- static void generate_histogram_gray (CFHistogram, Layer *, int alpha_dither);
- static void generate_histogram_rgb (CFHistogram, Layer *, int col_limit, int alpha_dither);
-
- static QuantizeObj* initialize_median_cut (int, int, ConvertDitherType,
- ConvertPaletteType, int);
-
- static void
- compute_color_rgb (QuantizeObj *quantobj,
- CFHistogram histogram,
- boxptr boxp,
- int icolor);
-
- static unsigned char found_cols[MAXNUMCOLORS][3];
- static int num_found_cols;
- static gboolean needs_quantize;
-
- static GtkWidget *build_palette_button (void);
-
- static gboolean UserHasWebPal = FALSE;
-
- PaletteEntries *theCustomPalette = NULL;
-
-
- /* Defaults */
- static int snum_cols = 256;
- static gboolean sfsdither_flag = TRUE;
- static gboolean sfslowbleeddither_flag = TRUE;
- static gboolean snodither_flag = FALSE;
- static gboolean sfixeddither_flag = FALSE;
- static gboolean smakepal_flag = TRUE;
- static gboolean salphadither_flag = FALSE;
- static gboolean sremdups_flag = TRUE;
- static gboolean swebpal_flag = FALSE;
- static gboolean scustompal_flag = FALSE;
- static gboolean smonopal_flag = FALSE;
- static gboolean sreusepal_flag = FALSE;
-
-
- void
- convert_to_rgb (GimpImage *gimage)
- {
- convert_image (gimage, RGB, 0, 0, 0, 0, 0);
- gdisplays_flush ();
- }
-
- void
- convert_to_grayscale (GimpImage* gimage)
- {
- convert_image (gimage, GRAY, 0, 0, 0, 0, 0);
- gdisplays_flush ();
- }
-
- void
- convert_to_indexed (GimpImage *gimage)
- {
- IndexedDialog *dialog;
- GtkWidget *main_vbox;
- GtkWidget *vbox;
- GtkWidget *hbox;
- GtkWidget *label;
- GtkObject *adjustment;
- GtkWidget *spinbutton;
- GtkWidget *frame;
- GtkWidget *custom_frame = NULL;
- GtkWidget *toggle;
- GSList *group = NULL;
-
- dialog = g_new (IndexedDialog, 1);
- dialog->gimage = gimage;
-
- dialog->custom_palette_button = NULL;
- dialog->palette_select = NULL;
-
- dialog->num_cols = snum_cols;
- dialog->nodither_flag = snodither_flag;
- dialog->fsdither_flag = sfsdither_flag;
- dialog->fslowbleeddither_flag = sfslowbleeddither_flag;
- dialog->fixeddither_flag = sfixeddither_flag;
- dialog->alphadither = salphadither_flag;
- dialog->remdups = sremdups_flag;
- dialog->makepal_flag = smakepal_flag;
- dialog->webpal_flag = swebpal_flag;
- dialog->custompal_flag = scustompal_flag;
- dialog->monopal_flag = smonopal_flag;
- dialog->reusepal_flag = sreusepal_flag;
-
- dialog->shell =
- gimp_dialog_new (_("Indexed Color Conversion"), "indexed_color_conversion",
- gimp_standard_help_func,
- "dialogs/convert_to_indexed.html",
- GTK_WIN_POS_NONE,
- FALSE, FALSE, TRUE,
-
- _("OK"), indexed_ok_callback,
- dialog, NULL, NULL, TRUE, FALSE,
- _("Cancel"), indexed_cancel_callback,
- dialog, NULL, NULL, FALSE, TRUE,
-
- NULL);
-
- main_vbox = gtk_vbox_new (FALSE, 2);
- gtk_container_set_border_width (GTK_CONTAINER (main_vbox), 4);
- gtk_container_add (GTK_CONTAINER (GTK_DIALOG (dialog->shell)->vbox),
- main_vbox);
- gtk_widget_show (main_vbox);
-
- frame = gtk_frame_new (_("General Palette Options"));
- gtk_box_pack_start (GTK_BOX (main_vbox), frame, FALSE, FALSE, 0);
- gtk_widget_show (frame);
-
- vbox = gtk_vbox_new (FALSE, 1);
- gtk_container_set_border_width (GTK_CONTAINER (vbox), 2);
- gtk_container_add (GTK_CONTAINER (frame), vbox);
- gtk_widget_show (vbox);
-
- /* 'generate palette' */
- hbox = gtk_hbox_new (FALSE, 4);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
-
- toggle = gtk_radio_button_new_with_label (NULL, _("Generate Optimal Palette:"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->makepal_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->makepal_flag);
- gtk_widget_show (toggle);
-
- if (dialog->num_cols == 256)
- {
- if ((!gimage_is_empty (gimage))
- &&
- (
- gimage->layers->next
- ||
- layer_has_alpha ((Layer *) gimage->layers->data)
- )
- )
- {
- dialog->num_cols = 255;
- }
- }
-
- spinbutton = gimp_spin_button_new (&adjustment, dialog->num_cols,
- 2, 256, 1, 5, 0, 1, 0);
- gtk_signal_connect (GTK_OBJECT (adjustment), "value_changed",
- GTK_SIGNAL_FUNC (gimp_int_adjustment_update),
- &(dialog->num_cols));
- gtk_box_pack_end (GTK_BOX (hbox), spinbutton, FALSE, FALSE, 0);
- gtk_widget_show (spinbutton);
-
- label = gtk_label_new (_("# of Colors:"));
- gtk_box_pack_end (GTK_BOX (hbox), label, FALSE, FALSE, 0);
- gtk_widget_show (label);
-
- gtk_widget_set_sensitive (GTK_WIDGET (spinbutton), dialog->num_cols);
- gtk_widget_set_sensitive (GTK_WIDGET (label), dialog->num_cols);
- gtk_object_set_data (GTK_OBJECT (toggle), "set_sensitive", spinbutton);
- gtk_object_set_data (GTK_OBJECT (spinbutton), "set_sensitive", label);
-
- gtk_widget_show (hbox);
-
- /* 'custom' palette from dialog */
- dialog->custom_palette_button = build_palette_button ();
- if (dialog->custom_palette_button)
- {
- /* create the custom_frame here, it'll be added later */
- custom_frame = gtk_frame_new (_("Custom Palette Options"));
- gtk_container_set_border_width (GTK_CONTAINER (custom_frame), 2);
-
- /* The remove-duplicates toggle */
- hbox = gtk_hbox_new (FALSE, 1);
- gtk_container_add (GTK_CONTAINER (custom_frame), hbox);
- toggle = gtk_check_button_new_with_label (_("Remove Unused Colors from Final Palette"));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle), dialog->remdups);
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->remdups));
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- /* 'custom' palette from dialog */
- hbox = gtk_hbox_new (FALSE, 4);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
- toggle = gtk_radio_button_new_with_label (group, _("Use Custom Palette:"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->custompal_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->custompal_flag);
- gtk_object_set_data (GTK_OBJECT (toggle), "set_sensitive", custom_frame);
- gtk_widget_show (toggle);
-
- gtk_signal_connect (GTK_OBJECT (dialog->custom_palette_button), "clicked",
- GTK_SIGNAL_FUNC (indexed_custom_palette_button_callback),
- dialog);
- gtk_box_pack_end (GTK_BOX (hbox), dialog->custom_palette_button, TRUE, TRUE, 0);
- gtk_widget_show (dialog->custom_palette_button);
- gtk_widget_show (hbox);
-
- gtk_widget_set_sensitive (GTK_WIDGET (custom_frame), dialog->custompal_flag);
- gtk_widget_set_sensitive (GTK_WIDGET (dialog->custom_palette_button), dialog->custompal_flag);
- gtk_object_set_data (GTK_OBJECT (toggle), "set_sensitive", custom_frame);
- gtk_object_set_data (GTK_OBJECT (custom_frame), "set_sensitive", dialog->custom_palette_button);
- }
-
- if (!UserHasWebPal)
- {
- /* 'web palette'
- * Only presented as an option to the user if they do not
- * already have the 'Web' GIMP palette installed on their
- * system.
- */
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
- toggle =
- gtk_radio_button_new_with_label (group, _("Use WWW-Optimized Palette"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->webpal_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->webpal_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
- }
-
- /* 'mono palette' */
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
- toggle =
- gtk_radio_button_new_with_label (group, _("Use Black/White (1-Bit) Palette"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->monopal_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->monopal_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- frame = gtk_frame_new (_("Dither Options"));
- gtk_box_pack_start (GTK_BOX (main_vbox), frame, FALSE, FALSE, 0);
- gtk_widget_show (frame);
-
- vbox = gtk_vbox_new (FALSE, 1);
- gtk_container_set_border_width (GTK_CONTAINER (vbox), 2);
- gtk_container_add (GTK_CONTAINER (frame), vbox);
- gtk_widget_show(vbox);
-
- /* The dither radio buttons */
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
-
- toggle = gtk_radio_button_new_with_label (NULL, _("No Color Dithering"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->nodither_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->nodither_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
-
- toggle = gtk_radio_button_new_with_label (group, _("Positioned Color Dithering"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->fixeddither_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->fixeddither_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
-
- toggle = gtk_radio_button_new_with_label (group, _("Floyd-Steinberg Color Dithering (Reduced Color Bleeding)"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->fslowbleeddither_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->fslowbleeddither_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
- toggle = gtk_radio_button_new_with_label (group, _("Floyd-Steinberg Color Dithering (Normal)"));
- group = gtk_radio_button_group (GTK_RADIO_BUTTON (toggle));
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->fsdither_flag));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->fsdither_flag);
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- /* The alpha-dither toggle */
- hbox = gtk_hbox_new (FALSE, 0);
- gtk_box_pack_start (GTK_BOX (vbox), hbox, FALSE, FALSE, 0);
- toggle = gtk_check_button_new_with_label (_("Enable Dithering of Transparency"));
- gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (toggle),
- dialog->alphadither);
- gtk_box_pack_start (GTK_BOX (hbox), toggle, FALSE, FALSE, 0);
- gtk_signal_connect (GTK_OBJECT (toggle), "toggled",
- GTK_SIGNAL_FUNC (gimp_toggle_button_update),
- &(dialog->alphadither));
- gtk_widget_show (toggle);
- gtk_widget_show (hbox);
-
- /* now add the custom_frame */
- if (custom_frame)
- {
- gtk_box_pack_start (GTK_BOX (main_vbox), custom_frame, FALSE, FALSE, 0);
- gtk_widget_show (custom_frame);
- }
-
- /* if the image isn't non-alpha/layered, set the default number of
- colours to one less than max, to leave room for a transparent index
- for transparent/animated GIFs */
- if ((!gimage_is_empty (gimage))
- &&
- (
- gimage->layers->next
- ||
- layer_has_alpha ((Layer *) gimage->layers->data)
- )
- )
- {
- frame = gtk_frame_new (_("[ Warning ]"));
- gtk_box_pack_start (GTK_BOX (main_vbox), frame, FALSE, FALSE, 0);
- gtk_widget_show (frame);
-
- vbox = gtk_vbox_new (FALSE, 1);
- gtk_container_set_border_width (GTK_CONTAINER (vbox), 2);
- gtk_container_add (GTK_CONTAINER (frame), vbox);
- gtk_widget_show (vbox);
-
- label = gtk_label_new
- (_("You are attempting to convert an image with alpha/layers "
- "from RGB/GRAY to INDEXED.\nYou should not generate a "
- "palette of more than 255 colors if you intend to create "
- "a transparent or animated GIF file from this image."));
- gtk_label_set_justify (GTK_LABEL (label), GTK_JUSTIFY_LEFT);
- gtk_label_set_line_wrap (GTK_LABEL (label), TRUE);
- gtk_container_add (GTK_CONTAINER (vbox), label);
- gtk_widget_show (label);
-
- }
-
- gtk_widget_show (dialog->shell);
- }
-
-
- static GtkWidget *
- build_palette_button (void)
- {
- GSList *list;
- PaletteEntries *entries;
- PaletteEntries *theWebPalette = NULL;
- int i, default_palette;
-
- UserHasWebPal = FALSE;
-
- if (!palette_entries_list)
- {
- palettes_init (FALSE);
- }
-
- list = palette_entries_list;
-
- if (!list)
- {
- return NULL;
- }
-
- for (i = 0, list = palette_entries_list, default_palette = -1;
- list;
- i++, list = g_slist_next (list))
- {
- entries = (PaletteEntries *) list->data;
-
- /* Preferentially, the initial default is 'Web' if available */
- if (theWebPalette == NULL &&
- g_strcasecmp (entries->name, "Web") == 0)
- {
- theWebPalette = entries;
- UserHasWebPal = TRUE;
- }
-
- /* We can't dither to > 256 colors */
- if (entries->n_colors <= 256)
- {
- if (theCustomPalette == entries)
- {
- default_palette = i;
- }
- }
- }
-
- /* default to first one with <= 256 colors
- (only used if 'web' palette not available) */
- if (default_palette == -1)
- {
- if (theWebPalette)
- {
- theCustomPalette = theWebPalette;
- default_palette = 1; /* dummy value */
- }
- else
- {
- for (i = 0, list = palette_entries_list;
- list && default_palette == -1;
- i++, list = g_slist_next (list))
- {
- entries = (PaletteEntries *) list->data;
-
- if (entries->n_colors <= 256)
- {
- theCustomPalette = entries;
- default_palette = i;
- }
- }
- }
- }
-
- if (default_palette == -1)
- return NULL;
- else
- return gtk_button_new_with_label (theCustomPalette->name);
- }
-
-
- static void
- indexed_ok_callback (GtkWidget *widget,
- gpointer data)
- {
- IndexedDialog *dialog;
- ConvertPaletteType palette_type;
- ConvertDitherType dither_type;
-
- dialog = (IndexedDialog *) data;
-
- if (dialog->webpal_flag) palette_type = WEB_PALETTE;
- else
- if (dialog->custompal_flag) palette_type = CUSTOM_PALETTE;
- else
- if (dialog->monopal_flag) palette_type = MONO_PALETTE;
- else
- if (dialog->makepal_flag) palette_type = MAKE_PALETTE;
- else
- palette_type = REUSE_PALETTE;
-
- if (dialog->nodither_flag) dither_type = NO_DITHER;
- else
- if (dialog->fsdither_flag) dither_type = FS_DITHER;
- else
- if (dialog->fslowbleeddither_flag) dither_type = FSLOWBLEED_DITHER;
- else
- dither_type = FIXED_DITHER;
-
- /* Close the dialogs when open because they're useless for indexed images
- and could crash the GIMP when used nevertheless */
-
- color_balance_dialog_hide();
- hue_saturation_dialog_hide ();
- brightness_contrast_dialog_hide();
- threshold_dialog_hide ();
- levels_dialog_hide ();
- curves_dialog_hide ();
- posterize_dialog_hide ();
-
- /* Convert the image to indexed color */
- convert_image (dialog->gimage, INDEXED, dialog->num_cols,
- dither_type, dialog->alphadither,
- dialog->remdups, palette_type);
- gdisplays_flush ();
-
- /* Save defaults for next time */
- snum_cols = dialog->num_cols;
- snodither_flag = dialog->nodither_flag;
- sfsdither_flag = dialog->fsdither_flag;
- sfslowbleeddither_flag = dialog->fslowbleeddither_flag;
- sfixeddither_flag = dialog->fixeddither_flag;
- salphadither_flag = dialog->alphadither;
- sremdups_flag = dialog->remdups;
- smakepal_flag = dialog->makepal_flag;
- swebpal_flag = dialog->webpal_flag;
- scustompal_flag = dialog->custompal_flag;
- smonopal_flag = dialog->monopal_flag;
- sreusepal_flag = dialog->reusepal_flag;
-
- if (dialog->palette_select)
- gtk_widget_destroy (dialog->palette_select->shell);
- gtk_widget_destroy (dialog->shell);
- g_free (dialog);
- dialog = NULL;
- }
-
- static void
- indexed_cancel_callback (GtkWidget *widget,
- gpointer data)
- {
- IndexedDialog *dialog;
-
- dialog = (IndexedDialog *) data;
-
- if (dialog->palette_select)
- gtk_widget_destroy (dialog->palette_select->shell);
- gtk_widget_destroy (dialog->shell);
- g_free (dialog);
- dialog = NULL;
- }
-
- static void
- indexed_palette_select_destroy_callback (GtkWidget *widget,
- gpointer data)
- {
- IndexedDialog *dialog = (IndexedDialog *)data;
-
- if (dialog)
- dialog->palette_select = NULL;
- }
-
- static gint
- indexed_palette_select_row_callback (GtkCList *clist,
- gint row,
- gint column,
- GdkEventButton *event,
- gpointer data)
- {
- IndexedDialog *dialog = (IndexedDialog *)data;
- PaletteEntries *p_entries;
-
- p_entries = (PaletteEntries *) gtk_clist_get_row_data (clist, row);
- if (p_entries)
- {
- if (p_entries->n_colors <= 256)
- {
- theCustomPalette = p_entries;
- gtk_label_set_text (GTK_LABEL (GTK_BIN(dialog->custom_palette_button)->child),
- theCustomPalette->name);
- }
- else
- {
- gtk_clist_unselect_row (clist, row, column);
- }
- }
- return FALSE;
- }
-
-
- static void
- indexed_custom_palette_button_callback (GtkWidget *widget,
- gpointer data)
- {
- IndexedDialog *dialog = (IndexedDialog *)data;
-
- if (dialog->palette_select == NULL)
- {
- dialog->palette_select = palette_select_new (_("Select Custom Palette"),
- theCustomPalette->name);
-
- gtk_signal_connect (GTK_OBJECT (dialog->palette_select->shell), "destroy",
- GTK_SIGNAL_FUNC (indexed_palette_select_destroy_callback),
- dialog);
- gtk_signal_connect (GTK_OBJECT (dialog->palette_select->clist), "select_row",
- GTK_SIGNAL_FUNC (indexed_palette_select_row_callback),
- dialog);
- }
- else
- {
- gdk_window_raise (dialog->palette_select->shell->window);
- }
- }
-
-
-
- /**********************************************************/
- typedef struct
- {
- signed long used_count;
- unsigned char initial_index;
- } palentryStruct;
-
- static int
- mapping_compare (const void *a, const void *b)
- {
- palentryStruct *m1 = (palentryStruct*)a;
- palentryStruct *m2 = (palentryStruct*)b;
-
- return (m2->used_count - m1->used_count);
- }
-
- /* FWIW, the make_remap_table() and mapping_compare() function source
- and palentryStruct may be re-used under the XFree86-style license.
- <adam@gimp.org> */
- static void
- make_remap_table (const unsigned char old_palette[],
- unsigned char new_palette[],
- const unsigned long index_used_count[],
- unsigned char remap_table[],
- int* num_entries)
- {
- int i,j,k;
- unsigned char temppal[256 * 3];
- unsigned long tempuse[256];
- unsigned long transmap[256];
- palentryStruct *palentries;
- int used = 0;
-
- memset(temppal, 0, 256 * 3);
- memset(tempuse, 0, 256 * sizeof(unsigned long));
- memset(transmap, 255, 256 * sizeof(unsigned long));
-
- /* First pass - only collect entries which are marked as
- being used at all in index_used_count. */
- for (i = 0; i < *num_entries; i++)
- {
- if (index_used_count[i])
- {
- temppal[used*3 + 0] = old_palette[i*3 + 0];
- temppal[used*3 + 1] = old_palette[i*3 + 1];
- temppal[used*3 + 2] = old_palette[i*3 + 2];
-
- tempuse[used] = index_used_count[i];
- transmap[i] = used;
-
- used++;
- }
- }
-
- /* Second pass - remove duplicates. (O(n^3), could do better!) */
- for (i = 0; i < used; i++)
- {
- for (j = 0; j < i; j++)
- {
- if ((temppal[i*3 + 1] == temppal[j*3 + 1]) &&
- (temppal[i*3 + 0] == temppal[j*3 + 0]) &&
- (temppal[i*3 + 2] == temppal[j*3 + 2]) &&
- tempuse[j] &&
- tempuse[i])
- {
- /* Move the 'used' tally from one to the other. */
- tempuse[i] += tempuse[j];
- /* zero one of them, deactivating its entry. */
- tempuse[j] = 0;
-
- /* change all mappings from this dead index
- to the live one. */
- for (k = 0; k < *num_entries; k++)
- {
- if (index_used_count[k] && (transmap[k] == j))
- transmap[k] = i;
- }
- }
- }
- }
-
- /* Third pass - rank all used indicies to the beginning of the
- palette. */
- palentries = g_malloc(used * sizeof(palentryStruct));
- for (i = 0; i < used; i++)
- {
- palentries[i].initial_index = i;
- palentries[i].used_count = tempuse[i];
- }
- qsort(palentries, used, sizeof(palentryStruct),
- &mapping_compare);
- for (i = 0; i < *num_entries; i++)
- {
- if (index_used_count[i])
- {
- for (j = 0; j < used; j++)
- {
- if ((transmap[i] == palentries[j].initial_index)
- && (palentries[j].used_count))
- {
- remap_table[i] = j;
- break;
- }
- }
- }
- }
- for (i = 0; i < *num_entries; i++)
- {
- if (index_used_count[i])
- {
- new_palette[remap_table[i]*3 + 0] = old_palette[i*3 + 0];
- new_palette[remap_table[i]*3 + 1] = old_palette[i*3 + 1];
- new_palette[remap_table[i]*3 + 2] = old_palette[i*3 + 2];
- }
- }
- *num_entries = 0;
- for (j = 0; j < used; j++)
- {
- if (palentries[j].used_count)
- {
- (*num_entries)++;
- }
- }
-
- g_free (palentries);
- }
-
- static void
- remap_indexed_layer (Layer *layer,
- unsigned char *remap_table,
- int num_entries)
- {
- PixelRegion srcPR, destPR;
- void* pr;
- int has_alpha;
- int pixels;
- unsigned char* src;
- unsigned char* dest;
-
- has_alpha = layer_has_alpha (layer) ? 1 : 0;
- pixel_region_init (&srcPR,
- GIMP_DRAWABLE(layer)->tiles, 0, 0,
- GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height,
- FALSE);
- pixel_region_init (&destPR,
- GIMP_DRAWABLE(layer)->tiles, 0, 0,
- GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height,
- TRUE);
-
- for (pr = pixel_regions_register (2, &srcPR, &destPR);
- pr != NULL;
- pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- pixels = srcPR.h * srcPR.w;
-
- while (pixels--)
- {
- if ((!has_alpha) || (has_alpha && src[ALPHA_I_PIX]))
- {
- dest[INDEXED_PIX] = remap_table[src[INDEXED_PIX]];
- }
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
-
- void
- convert_image (GImage *gimage,
- GimpImageBaseType new_type,
- /* The following three params used only for
- * new_type == INDEXED
- */
- int num_cols,
- ConvertDitherType dither,
- int alpha_dither,
- int remdups,
- ConvertPaletteType palette_type)
- {
- QuantizeObj *quantobj;
- Layer *layer;
- Layer *floating_layer;
- GimpImageBaseType old_type;
- GSList *list;
- GimpImageType new_layer_type;
- int new_layer_bytes;
- int has_alpha;
- TileManager *new_tiles;
-
- quantobj = NULL;
- new_layer_type = RGBA_GIMAGE;
- new_layer_bytes = 4;
-
- gimp_add_busy_cursors();
-
- /* Get the floating layer if one exists */
- floating_layer = gimage_floating_sel (gimage);
-
- undo_push_group_start (gimage, GIMAGE_MOD_UNDO);
-
- /* Relax the floating selection */
- if (floating_layer)
- floating_sel_relax (floating_layer, TRUE);
-
- /* Push the image size to the stack */
- undo_push_gimage_mod (gimage);
-
- /* Set the new base type */
- old_type = gimage->base_type;
- gimage->base_type = new_type;
-
- /* Convert to indexed? Build histogram if necessary. */
- if (new_type == INDEXED)
- {
- int i;
-
- /* don't dither if the input is grayscale and we are simply mapping every color */
- if (old_type == GRAY && num_cols == 256 && palette_type == MAKE_PALETTE)
- dither = NO_DITHER;
-
- quantobj = initialize_median_cut (old_type, num_cols, dither,
- palette_type, alpha_dither);
-
- if (palette_type == MAKE_PALETTE)
- {
- if (old_type == GRAY)
- zero_histogram_gray (quantobj->histogram);
- else
- zero_histogram_rgb (quantobj->histogram);
-
- /* To begin, assume that there are fewer colours in
- * the image than the user actually asked for. In that
- * case, we don't need to quantize or colour-dither.
- */
- needs_quantize = FALSE;
- num_found_cols = 0;
-
- /* Build the histogram */
- list = gimage->layers;
- while (list)
- {
- layer = (Layer *) list->data;
- list = g_slist_next (list);
- if (old_type == GRAY)
- generate_histogram_gray (quantobj->histogram, layer, alpha_dither);
- else
- generate_histogram_rgb (quantobj->histogram, layer, num_cols, alpha_dither);
- /*
- * Note: generate_histogram_rgb may set needs_quantize if
- * the image contains more colours than the limit specified
- * by the user.
- */
- }
- }
-
- if (
- (old_type == RGB) &&
- (!needs_quantize) &&
- (palette_type == MAKE_PALETTE)
- )
-
- {
- /* If this is an RGB image, and the user wanted a custom-built
- * generated palette, and this image has no more colours than
- * the user asked for, we don't need the first pass (quantization).
- *
- * There's also no point in dithering, since there's no error to
- * spread. So we destroy the old quantobj and make a new one
- * with the remapping function set to a special LUT-based
- * no-dither remapper.
- */
-
- quantobj->delete_func (quantobj);
- quantobj = initialize_median_cut (old_type, num_cols,
- NODESTRUCT_DITHER, palette_type,
- alpha_dither);
- /* We can skip the first pass (palette creation) */
-
- quantobj->actual_number_of_colors = num_found_cols;
- for (i = 0; i < num_found_cols; i++)
- {
- quantobj->cmap[i].red = found_cols[i][0];
- quantobj->cmap[i].green = found_cols[i][1];
- quantobj->cmap[i].blue = found_cols[i][2];
- }
- }
- else
- {
- (* quantobj->first_pass) (quantobj);
- }
- }
-
- /* Initialise data which must persist across indexed layer iterations */
- switch (new_type)
- {
- case INDEXED:
- if (quantobj->second_pass_init)
- (* quantobj->second_pass_init) (quantobj);
- break;
- default:
- break;
- }
-
- /* Convert all layers */
- list = gimage->layers;
- while (list)
- {
- layer = (Layer *) list->data;
- list = g_slist_next (list);
-
- has_alpha = layer_has_alpha (layer);
- switch (new_type)
- {
- case RGB:
- new_layer_type = (has_alpha) ? RGBA_GIMAGE : RGB_GIMAGE;
- new_layer_bytes = (has_alpha) ? 4 : 3;
- break;
- case GRAY:
- new_layer_type = (has_alpha) ? GRAYA_GIMAGE : GRAY_GIMAGE;
- new_layer_bytes = (has_alpha) ? 2 : 1;
- break;
- case INDEXED:
- new_layer_type = (has_alpha) ? INDEXEDA_GIMAGE : INDEXED_GIMAGE;
- new_layer_bytes = (has_alpha) ? 2 : 1;
- break;
- default:
- break;
- }
-
- new_tiles = tile_manager_new (GIMP_DRAWABLE(layer)->width,
- GIMP_DRAWABLE(layer)->height,
- new_layer_bytes);
-
- switch (new_type)
- {
- case RGB:
- rgb_converter (layer, new_tiles, old_type);
- break;
- case GRAY:
- grayscale_converter (layer, new_tiles, old_type);
- break;
- case INDEXED:
- (* quantobj->second_pass) (quantobj, layer, new_tiles);
- break;
- default:
- break;
- }
-
- /* Push the layer on the undo stack */
- undo_push_layer_mod (gimage, layer);
-
- GIMP_DRAWABLE (layer)->tiles = new_tiles;
- GIMP_DRAWABLE (layer)->bytes = new_layer_bytes;
- GIMP_DRAWABLE (layer)->type = new_layer_type;
- GIMP_DRAWABLE (layer)->has_alpha = GIMP_IMAGE_TYPE_HAS_ALPHA (new_layer_type);
- }
-
- /* colourmap stuff */
- if (new_type == INDEXED)
- {
- if (gimage->cmap)
- g_free (gimage->cmap);
- gimage->cmap = (unsigned char *) g_malloc (COLORMAP_SIZE);
-
- if (remdups &&
- ((palette_type == WEB_PALETTE) || (palette_type == CUSTOM_PALETTE)))
- {
- int i,j;
- unsigned char old_palette [256 * 3];
- unsigned char new_palette [256 * 3];
- unsigned char remap_table [256];
- int num_entries;
-
- for (i = 0, j = 0; i < quantobj->actual_number_of_colors; i++)
- {
- old_palette[j++] = quantobj->cmap[i].red;
- old_palette[j++] = quantobj->cmap[i].green;
- old_palette[j++] = quantobj->cmap[i].blue;
- }
-
- num_entries = quantobj->actual_number_of_colors;
-
- #if 1
- /* Generate a remapping table */
- make_remap_table (old_palette, new_palette,
- quantobj->index_used_count, remap_table, &num_entries);
-
- /* Convert all layers */
- list = gimage->layers;
- while (list)
- {
- layer = (Layer *) list->data;
- list = g_slist_next (list);
-
- remap_indexed_layer (layer, remap_table, num_entries);
- }
- #else
- memcpy(new_palette, old_palette, 256*3);
- #endif
-
- for (i = 0, j = 0; i < num_entries; i++)
- {
- gimage->cmap[j] = new_palette[j]; j++;
- gimage->cmap[j] = new_palette[j]; j++;
- gimage->cmap[j] = new_palette[j]; j++;
- }
- gimage->num_cols = num_entries;
- }
- else
- {
- int i,j;
-
- for (i = 0, j = 0; i < quantobj->actual_number_of_colors; i++)
- {
- gimage->cmap[j++] = quantobj->cmap[i].red;
- gimage->cmap[j++] = quantobj->cmap[i].green;
- gimage->cmap[j++] = quantobj->cmap[i].blue;
- }
- gimage->num_cols = quantobj->actual_number_of_colors;
- }
- }
-
- /* Delete the quantizer object, if there is one */
- if (quantobj)
- quantobj->delete_func (quantobj);
-
- /* Make sure the projection is up to date */
- gimage_projection_realloc (gimage);
-
- /* Rigor the floating selection */
- if (floating_layer)
- floating_sel_rigor (floating_layer, TRUE);
-
- undo_push_group_end (gimage);
-
- /* shrink wrap and update all views */
- layer_invalidate_previews (gimage);
- gimage_invalidate_preview (gimage);
- gdisplays_update_title (gimage);
- gdisplays_update_full (gimage);
-
- gimp_image_colormap_changed (gimage, -1);
-
- gimp_remove_busy_cursors(NULL);
- }
-
- static void
- rgb_converter (Layer *layer,
- TileManager *new_tiles,
- int old_type)
- {
- PixelRegion srcPR, destPR;
- int row, col;
- int offset;
- int has_alpha;
- unsigned char *src, *s;
- unsigned char *dest, *d;
- unsigned char *cmap;
- void *pr;
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
-
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
-
- switch (old_type)
- {
- case GRAY:
- for (row = 0; row < srcPR.h; row++)
- {
- s = src;
- d = dest;
- for (col = 0; col < srcPR.w; col++)
- {
- d[RED_PIX] = *s;
- d[GREEN_PIX] = *s;
- d[BLUE_PIX] = *s;
-
- d += 3;
- s++;
- if (has_alpha)
- *d++ = *s++;
- }
-
- src += srcPR.rowstride;
- dest += destPR.rowstride;
- }
- break;
- case INDEXED:
- cmap = drawable_cmap (GIMP_DRAWABLE(layer));
- for (row = 0; row < srcPR.h; row++)
- {
- s = src;
- d = dest;
- for (col = 0; col < srcPR.w; col++)
- {
- offset = *s++ * 3;
- d[RED_PIX] = cmap[offset + 0];
- d[GREEN_PIX] = cmap[offset + 1];
- d[BLUE_PIX] = cmap[offset + 2];
-
- d += 3;
- if (has_alpha)
- *d++ = *s++;
- }
-
- src += srcPR.rowstride;
- dest += destPR.rowstride;
- }
- break;
- default:
- break;
- }
- }
- }
-
- static void
- grayscale_converter (Layer *layer,
- TileManager *new_tiles,
- int old_type)
- {
- PixelRegion srcPR, destPR;
- int row, col;
- int offset, val;
- int has_alpha;
- unsigned char *src, *s;
- unsigned char *dest, *d;
- unsigned char *cmap;
- void *pr;
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
-
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
-
- switch (old_type)
- {
- case RGB:
- for (row = 0; row < srcPR.h; row++)
- {
- s = src;
- d = dest;
- for (col = 0; col < srcPR.w; col++)
- {
- val = INTENSITY (s[RED_PIX], s[GREEN_PIX], s[BLUE_PIX]);
- *d++ = (unsigned char) val;
- s += 3;
- if (has_alpha)
- *d++ = *s++;
- }
-
- src += srcPR.rowstride;
- dest += destPR.rowstride;
- }
- break;
- case INDEXED:
- cmap = drawable_cmap (GIMP_DRAWABLE(layer));
- for (row = 0; row < srcPR.h; row++)
- {
- s = src;
- d = dest;
- for (col = 0; col < srcPR.w; col++)
- {
- offset = *s++ * 3;
- val = INTENSITY (cmap[offset+0], cmap[offset+1], cmap[offset+2]);
- *d++ = (unsigned char) val;
- if (has_alpha)
- *d++ = *s++;
- }
-
- src += srcPR.rowstride;
- dest += destPR.rowstride;
- }
- break;
- default:
- break;
- }
- }
- }
-
-
- /*
- * Indexed color conversion machinery
- */
-
- static void
- zero_histogram_gray (CFHistogram histogram)
- {
- int i;
-
- for (i = 0; i < 256; i++)
- histogram[i] = 0;
- }
-
-
- static void
- zero_histogram_rgb (CFHistogram histogram)
- {
- int r, g, b;
-
- for (r = 0; r < HIST_R_ELEMS; r++)
- for (g = 0; g < HIST_G_ELEMS; g++)
- for (b = 0; b < HIST_B_ELEMS; b++)
- histogram[r*MR + g*MG + b] = 0;
- }
-
-
- static void
- generate_histogram_gray (CFHistogram histogram,
- Layer *layer,
- int alpha_dither)
- {
- PixelRegion srcPR;
- unsigned char *data;
- int size;
- void *pr;
- gboolean has_alpha;
-
- has_alpha = (gboolean) layer_has_alpha(layer);
-
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- for (pr = pixel_regions_register (1, &srcPR);
- pr != NULL;
- pr = pixel_regions_process (pr))
- {
- data = srcPR.data;
- size = srcPR.w * srcPR.h;
- while (size--)
- {
- histogram[*data] ++;
- data += srcPR.bytes;
- }
- }
- }
-
-
- static void
- generate_histogram_rgb (CFHistogram histogram,
- Layer *layer,
- int col_limit,
- int alpha_dither)
- {
- PixelRegion srcPR;
- unsigned char *data;
- int size;
- void *pr;
- ColorFreq *colfreq;
- gboolean has_alpha;
- int nfc_iter;
- int row, col, coledge;
- int offsetx, offsety;
-
- has_alpha = (gboolean) layer_has_alpha(layer);
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- /* g_print ("col_limit = %d, nfc = %d\n", col_limit, num_found_cols);*/
-
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0,
- GIMP_DRAWABLE(layer)->width,
- GIMP_DRAWABLE(layer)->height,
- FALSE);
- for (pr = pixel_regions_register (1, &srcPR);
- pr != NULL;
- pr = pixel_regions_process (pr))
- {
- data = srcPR.data;
- size = srcPR.w * srcPR.h;
-
- /*fprintf(stderr, " [%d,%d - %d,%d]", srcPR.x, srcPR.y, offsetx, offsety);*/
-
- if (needs_quantize)
- {
- if (alpha_dither)
- {
- /* if alpha-dithering, we need to be deterministic w.r.t. offsets */
- col = srcPR.x + offsetx;
- coledge = col + srcPR.w;
- row = srcPR.y + offsety;
-
- while (size--)
- {
- if (
- (
- has_alpha && (
- (data[ALPHA_PIX] << 6) >
- (255 * DM[col&DM_WIDTHMASK][row&DM_HEIGHTMASK])
- )
- )
- || (!has_alpha))
- {
- colfreq = & histogram[(data[RED_PIX] >> R_SHIFT) * MR +
- (data[GREEN_PIX] >> G_SHIFT) * MG +
- (data[BLUE_PIX] >> B_SHIFT)];
- (*colfreq)++;
- }
-
- col++;
- if (col == coledge)
- {
- col = srcPR.x + offsetx;
- row++;
- }
-
- data += srcPR.bytes;
- }
- }
- else
- {
- while (size--)
- {
- if (
- (
- has_alpha && (
- (data[ALPHA_PIX] > 127)
- )
- )
- || (!has_alpha))
- {
- colfreq = & histogram[(data[RED_PIX] >> R_SHIFT) * MR +
- (data[GREEN_PIX] >> G_SHIFT) * MG +
- (data[BLUE_PIX] >> B_SHIFT)];
- (*colfreq)++;
- }
- data += srcPR.bytes;
- }
- }
- }
- else
- {
- /* if alpha-dithering, we need to be deterministic w.r.t. offsets */
- col = srcPR.x + offsetx;
- coledge = col + srcPR.w;
- row = srcPR.y + offsety;
-
- while (size--)
- {
- if ((has_alpha && (alpha_dither ?
- ((data[ALPHA_PIX] << 6) > (255 * DM[col&DM_WIDTHMASK][row&DM_HEIGHTMASK])) :
- (data[ALPHA_PIX] > 127))) || (!has_alpha))
- {
- colfreq = & histogram[(data[RED_PIX] >> R_SHIFT) * MR +
- (data[GREEN_PIX] >> G_SHIFT) * MG +
- (data[BLUE_PIX] >> B_SHIFT)];
- (*colfreq)++;
-
- if (!needs_quantize)
- {
- for (nfc_iter = 0;
- nfc_iter < num_found_cols;
- nfc_iter++)
- {
- if (
- (data[RED_PIX] == found_cols[nfc_iter][0])
- &&
- (data[GREEN_PIX] == found_cols[nfc_iter][1])
- &&
- (data[BLUE_PIX] == found_cols[nfc_iter][2])
- )
- goto already_found;
- }
-
- /* Colour was not in the table of
- * existing colours
- */
-
- num_found_cols++;
-
- if (num_found_cols > col_limit)
- {
- /* There are more colours in the image
- * than were allowed. We switch to plain
- * histogram calculation with a view to
- * quantizing at a later stage.
- */
- needs_quantize = TRUE;
- /* g_print (_("\nmax colours exceeded - needs quantize.\n"));*/
- goto already_found;
- }
- else
- {
- /* Remember the new colour we just found.
- */
- found_cols[num_found_cols-1][0] = data[RED_PIX];
- found_cols[num_found_cols-1][1] = data[GREEN_PIX];
- found_cols[num_found_cols-1][2] = data[BLUE_PIX];
- }
- }
- }
- already_found:
-
- col++;
- if (col == coledge)
- {
- col = srcPR.x + offsetx;
- row++;
- }
-
- data += srcPR.bytes;
- }
- }
- }
-
- /* g_print ("O: col_limit = %d, nfc = %d\n", col_limit, num_found_cols);*/
- }
-
-
- static boxptr
- find_split_candidate (boxptr boxlist,
- int numboxes)
- {
- boxptr boxp;
- int i;
- guint64 maxc = 0;
- boxptr which = NULL;
-
- for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
- {
- if (boxp->volume > 0)
- {
- if (boxp->gerror*G_SCALE > maxc)
- {
- which = boxp;
- maxc = boxp->gerror*G_SCALE;
- }
- if (boxp->rerror*R_SCALE > maxc)
- {
- which = boxp;
- maxc = boxp->rerror*R_SCALE;
- }
- if (boxp->berror*B_SCALE > maxc)
- {
- which = boxp;
- maxc = boxp->berror*B_SCALE;
- }
- }
- }
-
- return which;
- }
-
-
- #if 0
- static boxptr
- find_biggest_color_pop (boxptr boxlist,
- int numboxes)
- /* Find the splittable box with the largest color population */
- /* Returns NULL if no splittable boxes remain */
- {
-
- }
- #endif
-
- static boxptr
- find_biggest_volume (boxptr boxlist,
- int numboxes)
- /* Find the splittable box with the largest (scaled) volume */
- /* Returns NULL if no splittable boxes remain */
- {
- boxptr boxp;
- int i;
- int maxv = 0;
- boxptr which = NULL;
-
- for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
- {
- if (boxp->volume > maxv)
- {
- which = boxp;
- maxv = boxp->volume;
- }
- }
-
- return which;
- }
-
-
- static void
- update_box_gray (CFHistogram histogram,
- boxptr boxp)
- /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
- /* and recompute its volume and population */
- {
- int i, min, max, dist;
- long ccount;
-
- min = boxp->Rmin;
- max = boxp->Rmax;
-
- if (max > min)
- for (i = min; i <= max; i++)
- {
- if (histogram[i] != 0)
- {
- boxp->Rmin = min = i;
- break;
- }
- }
-
- if (max > min)
- for (i = max; i >= min; i--)
- {
- if (histogram[i] != 0)
- {
- boxp->Rmax = max = i;
- break;
- }
- }
-
- /* Update box volume.
- * We use 2-norm rather than real volume here; this biases the method
- * against making long narrow boxes, and it has the side benefit that
- * a box is splittable iff norm > 0.
- * Since the differences are expressed in histogram-cell units,
- * we have to shift back to JSAMPLE units to get consistent distances;
- * after which, we scale according to the selected distance scale factors.
- */
- dist = max - min;
- boxp->volume = dist * dist;
-
- /* Now scan remaining volume of box and compute population */
- ccount = 0;
- for (i = min; i <= max; i++)
- if (histogram[i] != 0)
- ccount++;
-
- boxp->colorcount = ccount;
- }
-
- static void
- update_box_rgb (CFHistogram histogram,
- boxptr boxp)
- /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
- /* and recompute its volume, population and error */
- {
- ColorFreq * histp;
- int R,G,B;
- int Rmin,Rmax,Gmin,Gmax,Bmin,Bmax;
- int dist0,dist1,dist2;
- long ccount;
- guint64 tempRerror;
- guint64 tempGerror;
- guint64 tempBerror;
- QuantizeObj dummyqo;
- box dummybox;
-
- Rmin = boxp->Rmin; Rmax = boxp->Rmax;
- Gmin = boxp->Gmin; Gmax = boxp->Gmax;
- Bmin = boxp->Bmin; Bmax = boxp->Bmax;
-
- if (Rmax > Rmin)
- for (R = Rmin; R <= Rmax; R++)
- for (G = Gmin; G <= Gmax; G++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++)
- if (*histp++ != 0)
- {
- boxp->Rmin = Rmin = R;
- goto have_Rmin;
- }
- }
- have_Rmin:
- if (Rmax > Rmin)
- for (R = Rmax; R >= Rmin; R--)
- for (G = Gmin; G <= Gmax; G++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++)
- if (*histp++ != 0)
- {
- boxp->Rmax = Rmax = R;
- goto have_Rmax;
- }
- }
- have_Rmax:
- if (Gmax > Gmin)
- for (G = Gmin; G <= Gmax; G++)
- for (R = Rmin; R <= Rmax; R++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++)
- if (*histp++ != 0)
- {
- boxp->Gmin = Gmin = G;
- goto have_Gmin;
- }
- }
- have_Gmin:
- if (Gmax > Gmin)
- for (G = Gmax; G >= Gmin; G--)
- for (R = Rmin; R <= Rmax; R++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++)
- if (*histp++ != 0)
- {
- boxp->Gmax = Gmax = G;
- goto have_Gmax;
- }
- }
- have_Gmax:
- if (Bmax > Bmin)
- for (B = Bmin; B <= Bmax; B++)
- for (R = Rmin; R <= Rmax; R++)
- {
- histp = histogram + R*MR + Gmin*MG + B;
- for (G = Gmin; G <= Gmax; G++, histp += MG)
- if (*histp != 0)
- {
- boxp->Bmin = Bmin = B;
- goto have_Bmin;
- }
- }
- have_Bmin:
- if (Bmax > Bmin)
- for (B = Bmax; B >= Bmin; B--)
- for (R = Rmin; R <= Rmax; R++)
- {
- histp = histogram + R*MR + Gmin*MG + B;
- for (G = Gmin; G <= Gmax; G++, histp += MG)
- if (*histp != 0)
- {
- boxp->Bmax = Bmax = B;
- goto have_Bmax;
- }
- }
- have_Bmax:
-
- /* Update box volume.
- * We use 2-norm rather than real volume here; this biases the method
- * against making long narrow boxes, and it has the side benefit that
- * a box is splittable iff norm > 0.
- * Since the differences are expressed in histogram-cell units,
- * we have to shift back to JSAMPLE units to get consistent distances;
- * after which, we scale according to the selected distance scale factors.
- */
- dist0 = (( + Rmax - Rmin) << R_SHIFT) * R_SCALE;
- dist1 = (( + Gmax - Gmin) << G_SHIFT) * G_SCALE;
- dist2 = (( + Bmax - Bmin) << B_SHIFT) * B_SCALE;
- boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2;
-
- compute_color_rgb(&dummyqo, histogram, boxp, 0);
-
- /*printf("(%d %d %d)\n", dummyqo.cmap[0].red,dummyqo.cmap[0].green,dummyqo.cmap[0].blue);
- fflush(stdout);*/
-
- /* Now scan remaining volume of box and compute population */
- ccount = 0;
- boxp->error = 0;
- boxp->rerror = 0;
- boxp->gerror = 0;
- boxp->berror = 0;
- for (R = Rmin; R <= Rmax; R++)
- for (G = Gmin; G <= Gmax; G++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++, histp++)
- if (*histp != 0)
- {
- int ge, be, re;
-
- dummybox.Rmin = dummybox.Rmax = R;
- dummybox.Gmin = dummybox.Gmax = G;
- dummybox.Bmin = dummybox.Bmax = B;
- compute_color_rgb(&dummyqo, histogram, &dummybox, 1);
-
- re = dummyqo.cmap[0].red - dummyqo.cmap[1].red;
- ge = dummyqo.cmap[0].green - dummyqo.cmap[1].green;
- be = dummyqo.cmap[0].blue - dummyqo.cmap[1].blue;
-
- boxp->rerror += (*histp) * re*re;
- boxp->gerror += (*histp) * ge*ge;
- boxp->berror += (*histp) * be*be;
-
- boxp->error += (*histp) *
- (
- re*re*R_SCALE + ge*ge*G_SCALE + be*be*B_SCALE
- );
-
- ccount += *histp;
- }
- }
-
- /* Scan again, taking note of halfway error point for red axis */
- tempRerror = 0;
- boxp->Rhalferror = Rmin;
- for (R = Rmin; R < Rmax; R++)
- {
- dummybox.Rmin = dummybox.Rmax = R;
- for (G = Gmin; G <= Gmax; G++)
- {
- dummybox.Gmin = dummybox.Gmax = G;
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++, histp++)
- if (*histp != 0)
- {
- int re;
- dummybox.Bmin = dummybox.Bmax = B;
- compute_color_rgb(&dummyqo, histogram, &dummybox, 1);
-
- re = dummyqo.cmap[0].red - dummyqo.cmap[1].red;
-
- tempRerror += (*histp)*re*re;
-
- if (tempRerror*2 > boxp->rerror)
- goto green_axisscan;
- else
- boxp->Rhalferror = R;
- }
- }
- }
-
- green_axisscan:
- /* Scan again, taking note of halfway error point for green axis */
- tempGerror = 0;
- boxp->Ghalferror = Gmin;
- for (G = Gmin; G < Gmax; G++)
- {
- dummybox.Gmin = dummybox.Gmax = G;
- for (R = Rmin; R <= Rmax; R++)
- {
- dummybox.Rmin = dummybox.Rmax = R;
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++, histp++)
- if (*histp != 0)
- {
- int ge;
- dummybox.Bmin = dummybox.Bmax = B;
- compute_color_rgb(&dummyqo, histogram, &dummybox, 1);
-
- ge = dummyqo.cmap[0].green - dummyqo.cmap[1].green;
-
- tempGerror += (*histp)*ge*ge;
-
- if (tempGerror*2 > boxp->gerror)
- goto blue_axisscan;
- else
- boxp->Ghalferror = G;
- }
- }
- }
-
- blue_axisscan:
- /* Scan again, taking note of halfway error point for blue axis */
- tempBerror = 0;
- boxp->Bhalferror = Bmin;
- for (B = Bmin; B < Bmax; B++)
- {
- dummybox.Bmin = dummybox.Bmax = B;
- for (R = Rmin; R <= Rmax; R++)
- {
- dummybox.Rmin = dummybox.Rmax = R;
- for (G = Gmin; G <= Gmax; G++)
- {
- histp = histogram + R*MR + G*MG + B;
- if (*histp != 0)
- {
- int be;
- dummybox.Gmin = dummybox.Gmax = G;
- compute_color_rgb(&dummyqo, histogram, &dummybox, 1);
-
- be = dummyqo.cmap[0].blue - dummyqo.cmap[1].blue;
-
- tempBerror += (*histp)*be*be;
-
- if (tempBerror*2 > boxp->berror)
- goto finished_axesscan;
- else
- boxp->Bhalferror = B;
- }
- }
- }
- }
- finished_axesscan:
-
- /*
- boxp->Rhalferror = (Rmin+Rmax)/2;
- boxp->Ghalferror = (Gmin+Gmax)/2;
- boxp->Bhalferror = (Bmin+Bmax)/2;
- */
-
- /*boxp->error = (sqrt((double)(boxp->error/ccount)));*/
- /* boxp->rerror = (sqrt((double)((boxp->rerror)/ccount)));
- boxp->gerror = (sqrt((double)((boxp->gerror)/ccount)));
- boxp->berror = (sqrt((double)((boxp->berror)/ccount)));*/
- /*printf(":%lld / %ld: ", boxp->error, ccount);
- printf("(%d-%d-%d)(%d-%d-%d)(%d-%d-%d)\n",
- Rmin, boxp->Rhalferror, Rmax,
- Gmin, boxp->Ghalferror, Gmax,
- Bmin, boxp->Bhalferror, Bmax
- );
- fflush(stdout);*/
-
- boxp->colorcount = ccount;
- }
-
-
- static int
- median_cut_gray (CFHistogram histogram,
- boxptr boxlist,
- int numboxes,
- int desired_colors)
- /* Repeatedly select and split the largest box until we have enough boxes */
- {
- int lb;
- boxptr b1, b2;
-
- while (numboxes < desired_colors)
- {
- /* Select box to split.
- * Current algorithm: by population for first half, then by volume.
- */
- #if 0
- if (numboxes*2 <= desired_colors)
- {
- b1 = find_biggest_color_pop (boxlist, numboxes);
- }
- else
- #endif
- {
- b1 = find_biggest_volume (boxlist, numboxes);
- }
-
- if (b1 == NULL) /* no splittable boxes left! */
- break;
-
- b2 = boxlist + numboxes; /* where new box will go */
- /* Copy the color bounds to the new box. */
- b2->Rmax = b1->Rmax;
- b2->Rmin = b1->Rmin;
-
- /* Current algorithm: split at halfway point.
- * (Since the box has been shrunk to minimum volume,
- * any split will produce two nonempty subboxes.)
- * Note that lb value is max for lower box, so must be < old max.
- */
- lb = (b1->Rmax + b1->Rmin) / 2;
- b1->Rmax = lb;
- b2->Rmin = lb + 1;
-
- /* Update stats for boxes */
- update_box_gray (histogram, b1);
- update_box_gray (histogram, b2);
- numboxes++;
- }
-
- return numboxes;
- }
-
- static int
- median_cut_rgb (CFHistogram histogram,
- boxptr boxlist,
- int numboxes,
- int desired_colors)
- /* Repeatedly select and split the largest box until we have enough boxes */
- {
- int n,lb;
- guint64 R,G,B,cmax;
- boxptr b1,b2;
-
- while (numboxes < desired_colors) {
- #if 0
- /* Select box to split.
- * Current algorithm: by population for first half, then by volume.
- */
- if (1 || numboxes*2 <= desired_colors)
- {
- g_print ("O ");
- b1 = find_biggest_color_pop (boxlist, numboxes);
- }
- else
- {
- g_print (". ");
- b1 = find_biggest_volume (boxlist, numboxes);
- }
- #endif
- b1 = find_split_candidate (boxlist, numboxes);
-
- if (b1 == NULL) /* no splittable boxes left! */
- break;
- b2 = boxlist + numboxes; /* where new box will go */
- /* Copy the color bounds to the new box. */
- b2->Rmax = b1->Rmax; b2->Gmax = b1->Gmax; b2->Bmax = b1->Bmax;
- b2->Rmin = b1->Rmin; b2->Gmin = b1->Gmin; b2->Bmin = b1->Bmin;
- /* Choose which axis to split the box on.
- * See notes in update_box about scaling distances.
- */
- /*
- R = ((b1->Rmax - b1->Rmin) << R_SHIFT) * R_SCALE;
- G = ((b1->Gmax - b1->Gmin) << G_SHIFT) * G_SCALE;
- B = ((b1->Bmax - b1->Bmin) << B_SHIFT) * B_SCALE;
- */
- R = R_SCALE*b1->rerror;/* * (((b1->Rmax - b1->Rmin) << R_SHIFT)) * R_SCALE; */
- G = G_SCALE*b1->gerror;/* * (((b1->Gmax - b1->Gmin) << G_SHIFT)) * G_SCALE; */
- B = B_SCALE*b1->berror;/* * (((b1->Bmax - b1->Bmin) << B_SHIFT)) * B_SCALE; */
- /* We want to break any ties in favor of green, then red, blue last.
- */
- cmax = G; n = 1;
- if (R > cmax) { cmax = R; n = 0; }
- if (B > cmax) { n = 2; }
-
- /* Choose split point along selected axis, and update box bounds.
- * Note that lb value is max for lower box, so must be < old max.
- */
- switch (n)
- {
- case 0:
- lb = b1->Rhalferror;/* *0 + (b1->Rmax + b1->Rmin) / 2; */
- b1->Rmax = lb;
- b2->Rmin = lb+1;
- g_assert(b1->Rmax >= b1->Rmin);
- g_assert(b2->Rmax >= b2->Rmin);
- break;
- case 1:
- lb = b1->Ghalferror;/* *0 + (b1->Gmax + b1->Gmin) / 2; */
- b1->Gmax = lb;
- b2->Gmin = lb+1;
- g_assert(b1->Gmax >= b1->Gmin);
- g_assert(b2->Gmax >= b2->Gmin);
- break;
- case 2:
- lb = b1->Bhalferror;/* *0 + (b1->Bmax + b1->Bmin) / 2; */
- b1->Bmax = lb;
- b2->Bmin = lb+1;
- g_assert(b1->Bmax >= b1->Bmin);
- g_assert(b2->Bmax >= b2->Bmin);
- break;
- }
- /* Update stats for boxes */
- update_box_rgb (histogram, b1);
- update_box_rgb (histogram, b2);
- numboxes++;
- }
- return numboxes;
- }
-
-
- static void
- compute_color_gray (QuantizeObj *quantobj,
- CFHistogram histogram,
- boxptr boxp,
- int icolor)
- /* Compute representative color for a box, put it in colormap[icolor] */
- {
- int i, min, max;
- long count;
- long total;
- long gtotal;
-
- min = boxp->Rmin;
- max = boxp->Rmax;
-
- total = 0;
- gtotal = 0;
-
- for (i = min; i <= max; i++)
- {
- count = histogram[i];
- if (count != 0)
- {
- total += count;
- gtotal += i * count;
- }
- }
-
- if (total != 0)
- {
- quantobj->cmap[icolor].red = (gtotal + (total >> 1)) / total;
- quantobj->cmap[icolor].green = quantobj->cmap[icolor].red;
- quantobj->cmap[icolor].blue = quantobj->cmap[icolor].red;
- }
- else /* The only situation where total==0 is if the image was null or
- * all-transparent. In that case we just put a dummy value in
- * the colourmap.
- */
- {
- quantobj->cmap[icolor].red =
- quantobj->cmap[icolor].green =
- quantobj->cmap[icolor].blue = 0;
- }
- }
-
- static void
- compute_color_rgb (QuantizeObj *quantobj,
- CFHistogram histogram,
- boxptr boxp,
- int icolor)
- /* Compute representative color for a box, put it in colormap[icolor] */
- {
- /* Current algorithm: mean weighted by pixels (not colors) */
- /* Note it is important to get the rounding correct! */
- ColorFreq * histp;
- int R, G, B;
- int Rmin, Rmax;
- int Gmin, Gmax;
- int Bmin, Bmax;
- long count;
- long total = 0;
- long Rtotal = 0;
- long Gtotal = 0;
- long Btotal = 0;
-
- Rmin = boxp->Rmin; Rmax = boxp->Rmax;
- Gmin = boxp->Gmin; Gmax = boxp->Gmax;
- Bmin = boxp->Bmin; Bmax = boxp->Bmax;
-
- for (R = Rmin; R <= Rmax; R++)
- for (G = Gmin; G <= Gmax; G++)
- {
- histp = histogram + R*MR + G*MG + Bmin;
- for (B = Bmin; B <= Bmax; B++)
- {
- if ((count = *histp++) != 0)
- {
- total += count;
- Rtotal += ((R << R_SHIFT) + ((1<<R_SHIFT)>>1)) * count;
- Gtotal += ((G << G_SHIFT) + ((1<<G_SHIFT)>>1)) * count;
- Btotal += ((B << B_SHIFT) + ((1<<B_SHIFT)>>1)) * count;
- }
- }
- }
-
- if (total != 0)
- {
- quantobj->cmap[icolor].red = (Rtotal + (total>>1)) / total;
- quantobj->cmap[icolor].green = (Gtotal + (total>>1)) / total;
- quantobj->cmap[icolor].blue = (Btotal + (total>>1)) / total;
- }
- else /* The only situation where total==0 is if the image was null or
- * all-transparent. In that case we just put a dummy value in
- * the colourmap.
- */
- {
- quantobj->cmap[icolor].red =
- quantobj->cmap[icolor].green =
- quantobj->cmap[icolor].blue = 0;
- }
- }
-
-
- static void
- select_colors_gray (QuantizeObj *quantobj,
- CFHistogram histogram)
- /* Master routine for color selection */
- {
- boxptr boxlist;
- int numboxes;
- int desired = quantobj->desired_number_of_colors;
- int i;
-
- /* Allocate workspace for box list */
- boxlist = (boxptr) g_malloc ( desired * sizeof(box) );
-
- /* Initialize one box containing whole space */
- numboxes = 1;
- boxlist[0].Rmin = 0;
- boxlist[0].Rmax = 255;
- /* Shrink it to actually-used volume and set its statistics */
- update_box_gray (histogram, boxlist);
- /* Perform median-cut to produce final box list */
- numboxes = median_cut_gray (histogram, boxlist, numboxes, desired);
-
- quantobj->actual_number_of_colors = numboxes;
- /* Compute the representative color for each box, fill colormap */
- for (i = 0; i < numboxes; i++)
- compute_color_gray (quantobj, histogram, boxlist + i, i);
- }
-
-
- static void
- select_colors_rgb (QuantizeObj *quantobj,
- CFHistogram histogram)
- /* Master routine for color selection */
- {
- boxptr boxlist;
- int numboxes;
- int desired = quantobj->desired_number_of_colors;
- int i;
-
- /* Allocate workspace for box list */
- boxlist = (boxptr) g_malloc ( desired * sizeof(box) );
-
- /* Initialize one box containing whole space */
- numboxes = 1;
- boxlist[0].Rmin = 0;
- boxlist[0].Rmax = (1 << PRECISION_R) - 1;
- boxlist[0].Gmin = 0;
- boxlist[0].Gmax = (1 << PRECISION_G) - 1;
- boxlist[0].Bmin = 0;
- boxlist[0].Bmax = (1 << PRECISION_B) - 1;
- /* Shrink it to actually-used volume and set its statistics */
- update_box_rgb (histogram, boxlist);
- /* Perform median-cut to produce final box list */
- numboxes = median_cut_rgb (histogram, boxlist, numboxes, desired);
-
- quantobj->actual_number_of_colors = numboxes;
- /* Compute the representative color for each box, fill colormap */
- for (i = 0; i < numboxes; i++)
- compute_color_rgb (quantobj, histogram, boxlist + i, i);
- }
-
-
- /*
- * These routines are concerned with the time-critical task of mapping input
- * colors to the nearest color in the selected colormap.
- *
- * We re-use the histogram space as an "inverse color map", essentially a
- * cache for the results of nearest-color searches. All colors within a
- * histogram cell will be mapped to the same colormap entry, namely the one
- * closest to the cell's center. This may not be quite the closest entry to
- * the actual input color, but it's almost as good. A zero in the cache
- * indicates we haven't found the nearest color for that cell yet; the array
- * is cleared to zeroes before starting the mapping pass. When we find the
- * nearest color for a cell, its colormap index plus one is recorded in the
- * cache for future use. The pass2 scanning routines call fill_inverse_cmap
- * when they need to use an unfilled entry in the cache.
- *
- * Our method of efficiently finding nearest colors is based on the "locally
- * sorted search" idea described by Heckbert and on the incremental distance
- * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
- * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
- * the distances from a given colormap entry to each cell of the histogram can
- * be computed quickly using an incremental method: the differences between
- * distances to adjacent cells themselves differ by a constant. This allows a
- * fairly fast implementation of the "brute force" approach of computing the
- * distance from every colormap entry to every histogram cell. Unfortunately,
- * it needs a work array to hold the best-distance-so-far for each histogram
- * cell (because the inner loop has to be over cells, not colormap entries).
- * The work array elements have to be ints, so the work array would need
- * 256Kb at our recommended precision. This is not feasible in DOS machines.
- *
- * To get around these problems, we apply Thomas' method to compute the
- * nearest colors for only the cells within a small subbox of the histogram.
- * The work array need be only as big as the subbox, so the memory usage
- * problem is solved. Furthermore, we need not fill subboxes that are never
- * referenced in pass2; many images use only part of the color gamut, so a
- * fair amount of work is saved. An additional advantage of this
- * approach is that we can apply Heckbert's locality criterion to quickly
- * eliminate colormap entries that are far away from the subbox; typically
- * three-fourths of the colormap entries are rejected by Heckbert's criterion,
- * and we need not compute their distances to individual cells in the subbox.
- * The speed of this approach is heavily influenced by the subbox size: too
- * small means too much overhead, too big loses because Heckbert's criterion
- * can't eliminate as many colormap entries. Empirically the best subbox
- * size seems to be about 1/512th of the histogram (1/8th in each direction).
- *
- * Thomas' article also describes a refined method which is asymptotically
- * faster than the brute-force method, but it is also far more complex and
- * cannot efficiently be applied to small subboxes. It is therefore not
- * useful for programs intended to be portable to DOS machines. On machines
- * with plenty of memory, filling the whole histogram in one shot with Thomas'
- * refined method might be faster than the present code --- but then again,
- * it might not be any faster, and it's certainly more complicated.
- */
-
-
- /* log2(histogram cells in update box) for each axis; this can be adjusted */
- #define BOX_R_LOG (PRECISION_R-3)
- #define BOX_G_LOG (PRECISION_G-3)
- #define BOX_B_LOG (PRECISION_B-3)
-
- #define BOX_R_ELEMS (1<<BOX_R_LOG) /* # of hist cells in update box */
- #define BOX_G_ELEMS (1<<BOX_G_LOG)
- #define BOX_B_ELEMS (1<<BOX_B_LOG)
-
- #define BOX_R_SHIFT (R_SHIFT + BOX_R_LOG)
- #define BOX_G_SHIFT (G_SHIFT + BOX_G_LOG)
- #define BOX_B_SHIFT (B_SHIFT + BOX_B_LOG)
-
-
- /*
- * The next three routines implement inverse colormap filling. They could
- * all be folded into one big routine, but splitting them up this way saves
- * some stack space (the mindist[] and bestdist[] arrays need not coexist)
- * and may allow some compilers to produce better code by registerizing more
- * inner-loop variables.
- */
-
- static int
- find_nearby_colors (QuantizeObj *quantobj,
- int minR,
- int minG,
- int minB,
- int colorlist[])
- /* Locate the colormap entries close enough to an update box to be candidates
- * for the nearest entry to some cell(s) in the update box. The update box
- * is specified by the center coordinates of its first cell. The number of
- * candidate colormap entries is returned, and their colormap indexes are
- * placed in colorlist[].
- * This routine uses Heckbert's "locally sorted search" criterion to select
- * the colors that need further consideration.
- */
- {
- int numcolors = quantobj->actual_number_of_colors;
- int maxR, maxG, maxB;
- int centerR, centerG, centerB;
- int i, x, ncolors;
- int minmaxdist, min_dist, max_dist, tdist;
- int mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */
-
- /* Compute true coordinates of update box's upper corner and center.
- * Actually we compute the coordinates of the center of the upper-corner
- * histogram cell, which are the upper bounds of the volume we care about.
- * Note that since ">>" rounds down, the "center" values may be closer to
- * min than to max; hence comparisons to them must be "<=", not "<".
- */
- maxR = minR + ((1 << BOX_R_SHIFT) - (1 << R_SHIFT));
- centerR = (minR + maxR) >> 1;
- maxG = minG + ((1 << BOX_G_SHIFT) - (1 << G_SHIFT));
- centerG = (minG + maxG) >> 1;
- maxB = minB + ((1 << BOX_B_SHIFT) - (1 << B_SHIFT));
- centerB = (minB + maxB) >> 1;
-
- /* For each color in colormap, find:
- * 1. its minimum squared-distance to any point in the update box
- * (zero if color is within update box);
- * 2. its maximum squared-distance to any point in the update box.
- * Both of these can be found by considering only the corners of the box.
- * We save the minimum distance for each color in mindist[];
- * only the smallest maximum distance is of interest.
- */
- minmaxdist = 0x7FFFFFFFL;
-
- for (i = 0; i < numcolors; i++) {
- /* We compute the squared-R-distance term, then add in the other two. */
- x = quantobj->cmap[i].red;
- if (x < minR) {
- tdist = (x - minR) * R_SCALE;
- min_dist = tdist*tdist;
- tdist = (x - maxR) * R_SCALE;
- max_dist = tdist*tdist;
- } else if (x > maxR) {
- tdist = (x - maxR) * R_SCALE;
- min_dist = tdist*tdist;
- tdist = (x - minR) * R_SCALE;
- max_dist = tdist*tdist;
- } else {
- /* within cell range so no contribution to min_dist */
- min_dist = 0;
- if (x <= centerR) {
- tdist = (x - maxR) * R_SCALE;
- max_dist = tdist*tdist;
- } else {
- tdist = (x - minR) * R_SCALE;
- max_dist = tdist*tdist;
- }
- }
-
- x = quantobj->cmap[i].green;
- if (x < minG) {
- tdist = (x - minG) * G_SCALE;
- min_dist += tdist*tdist;
- tdist = (x - maxG) * G_SCALE;
- max_dist += tdist*tdist;
- } else if (x > maxG) {
- tdist = (x - maxG) * G_SCALE;
- min_dist += tdist*tdist;
- tdist = (x - minG) * G_SCALE;
- max_dist += tdist*tdist;
- } else {
- /* within cell range so no contribution to min_dist */
- if (x <= centerG) {
- tdist = (x - maxG) * G_SCALE;
- max_dist += tdist*tdist;
- } else {
- tdist = (x - minG) * G_SCALE;
- max_dist += tdist*tdist;
- }
- }
-
- x = quantobj->cmap[i].blue;
- if (x < minB) {
- tdist = (x - minB) * B_SCALE;
- min_dist += tdist*tdist;
- tdist = (x - maxB) * B_SCALE;
- max_dist += tdist*tdist;
- } else if (x > maxB) {
- tdist = (x - maxB) * B_SCALE;
- min_dist += tdist*tdist;
- tdist = (x - minB) * B_SCALE;
- max_dist += tdist*tdist;
- } else {
- /* within cell range so no contribution to min_dist */
- if (x <= centerB) {
- tdist = (x - maxB) * B_SCALE;
- max_dist += tdist*tdist;
- } else {
- tdist = (x - minB) * B_SCALE;
- max_dist += tdist*tdist;
- }
- }
-
- mindist[i] = min_dist; /* save away the results */
- if (max_dist < minmaxdist)
- minmaxdist = max_dist;
- }
-
- /* Now we know that no cell in the update box is more than minmaxdist
- * away from some colormap entry. Therefore, only colors that are
- * within minmaxdist of some part of the box need be considered.
- */
- ncolors = 0;
- for (i = 0; i < numcolors; i++) {
- if (mindist[i] <= minmaxdist)
- colorlist[ncolors++] = i;
- }
- return ncolors;
- }
-
-
- static void
- find_best_colors (QuantizeObj *quantobj,
- int minR,
- int minG,
- int minB,
- int numcolors,
- int colorlist[],
- int bestcolor[])
- /* Find the closest colormap entry for each cell in the update box,
- * given the list of candidate colors prepared by find_nearby_colors.
- * Return the indexes of the closest entries in the bestcolor[] array.
- * This routine uses Thomas' incremental distance calculation method to
- * find the distance from a colormap entry to successive cells in the box.
- */
- {
- int iR, iG, iB;
- int i, icolor;
- int * bptr; /* pointer into bestdist[] array */
- int * cptr; /* pointer into bestcolor[] array */
- int dist0, dist1; /* initial distance values */
- int dist2; /* current distance in inner loop */
- int xx0, xx1; /* distance increments */
- int xx2;
- int inR, inG, inB; /* initial values for increments */
-
- /* This array holds the distance to the nearest-so-far color for each cell */
- int bestdist[BOX_R_ELEMS * BOX_G_ELEMS * BOX_B_ELEMS];
-
- /* Initialize best-distance for each cell of the update box */
- bptr = bestdist;
- for (i = BOX_R_ELEMS*BOX_G_ELEMS*BOX_B_ELEMS-1; i >= 0; i--)
- *bptr++ = 0x7FFFFFFFL;
-
- /* For each color selected by find_nearby_colors,
- * compute its distance to the center of each cell in the box.
- * If that's less than best-so-far, update best distance and color number.
- */
-
- /* Nominal steps between cell centers ("x" in Thomas article) */
- #define STEP_R ((1 << R_SHIFT) * R_SCALE)
- #define STEP_G ((1 << G_SHIFT) * G_SCALE)
- #define STEP_B ((1 << B_SHIFT) * B_SCALE)
-
- for (i = 0; i < numcolors; i++) {
- icolor = colorlist[i];
- /* Compute (square of) distance from minR/G/B to this color */
- inR = (minR - quantobj->cmap[icolor].red) * R_SCALE;
- dist0 = inR*inR;
- inG = (minG - quantobj->cmap[icolor].green) * G_SCALE;
- dist0 += inG*inG;
- inB = (minB - quantobj->cmap[icolor].blue) * B_SCALE;
- dist0 += inB*inB;
- /* Form the initial difference increments */
- inR = inR * (2 * STEP_R) + STEP_R * STEP_R;
- inG = inG * (2 * STEP_G) + STEP_G * STEP_G;
- inB = inB * (2 * STEP_B) + STEP_B * STEP_B;
- /* Now loop over all cells in box, updating distance per Thomas method */
- bptr = bestdist;
- cptr = bestcolor;
- xx0 = inR;
- for (iR = BOX_R_ELEMS-1; iR >= 0; iR--) {
- dist1 = dist0;
- xx1 = inG;
- for (iG = BOX_G_ELEMS-1; iG >= 0; iG--) {
- dist2 = dist1;
- xx2 = inB;
- for (iB = BOX_B_ELEMS-1; iB >= 0; iB--) {
- if (dist2 < *bptr) {
- *bptr = dist2;
- *cptr = icolor;
- }
- dist2 += xx2;
- xx2 += 2 * STEP_B * STEP_B;
- bptr++;
- cptr++;
- }
- dist1 += xx1;
- xx1 += 2 * STEP_G * STEP_G;
- }
- dist0 += xx0;
- xx0 += 2 * STEP_R * STEP_R;
- }
- }
- }
-
-
- static void
- fill_inverse_cmap_gray (QuantizeObj *quantobj,
- CFHistogram histogram,
- int pixel)
- /* Fill the inverse-colormap entries in the update box that contains */
- /* histogram cell R/G/B. (Only that one cell MUST be filled, but */
- /* we can fill as many others as we wish.) */
- {
- Color *cmap;
- long dist;
- long mindist;
- int mindisti;
- int i;
-
- cmap = quantobj->cmap;
-
- mindist = 65536;
- mindisti = -1;
-
- for (i = 0; i < quantobj->actual_number_of_colors; i++)
- {
- dist = pixel - cmap[i].red;
- dist *= dist;
-
- if (dist < mindist)
- {
- mindist = dist;
- mindisti = i;
- }
- }
-
- if (i >= 0)
- histogram[pixel] = mindisti + 1;
- }
-
-
- static void
- fill_inverse_cmap_rgb (QuantizeObj *quantobj,
- CFHistogram histogram,
- int R,
- int G,
- int B)
- /* Fill the inverse-colormap entries in the update box that contains */
- /* histogram cell R/G/B. (Only that one cell MUST be filled, but */
- /* we can fill as many others as we wish.) */
- {
- int minR, minG, minB; /* lower left corner of update box */
- int iR, iG, iB;
- int * cptr; /* pointer into bestcolor[] array */
- ColorFreq * cachep; /* pointer into main cache array */
- /* This array lists the candidate colormap indexes. */
- int colorlist[MAXNUMCOLORS];
- int numcolors; /* number of candidate colors */
- /* This array holds the actually closest colormap index for each cell. */
- int bestcolor[BOX_R_ELEMS * BOX_G_ELEMS * BOX_B_ELEMS];
-
- /* Convert cell coordinates to update box id */
- R >>= BOX_R_LOG;
- G >>= BOX_G_LOG;
- B >>= BOX_B_LOG;
-
- /* Compute true coordinates of update box's origin corner.
- * Actually we compute the coordinates of the center of the corner
- * histogram cell, which are the lower bounds of the volume we care about.
- */
- minR = (R << BOX_R_SHIFT) + ((1 << R_SHIFT) >> 1);
- minG = (G << BOX_G_SHIFT) + ((1 << G_SHIFT) >> 1);
- minB = (B << BOX_B_SHIFT) + ((1 << B_SHIFT) >> 1);
-
- /* Determine which colormap entries are close enough to be candidates
- * for the nearest entry to some cell in the update box.
- */
- numcolors = find_nearby_colors (quantobj, minR, minG, minB, colorlist);
-
- /* Determine the actually nearest colors. */
- find_best_colors (quantobj, minR, minG, minB, numcolors, colorlist,
- bestcolor);
-
- /* Save the best color numbers (plus 1) in the main cache array */
- R <<= BOX_R_LOG; /* convert id back to base cell indexes */
- G <<= BOX_G_LOG;
- B <<= BOX_B_LOG;
- cptr = bestcolor;
- for (iR = 0; iR < BOX_R_ELEMS; iR++) {
- for (iG = 0; iG < BOX_G_ELEMS; iG++) {
- cachep = & histogram[(R+iR)*MR+(G+iG)*MG+B];
- for (iB = 0; iB < BOX_B_ELEMS; iB++) {
- *cachep++ = (*cptr++) + 1;
- }
- }
- }
- }
-
-
- /* This is pass 1 */
-
- static void
- median_cut_pass1_gray (QuantizeObj *quantobj)
- {
- select_colors_gray (quantobj, quantobj->histogram);
- }
-
-
- static void
- median_cut_pass1_rgb (QuantizeObj *quantobj)
- {
- select_colors_rgb (quantobj, quantobj->histogram);
- }
-
-
- static void
- monopal_pass1 (QuantizeObj *quantobj)
- {
- quantobj -> actual_number_of_colors = 2;
- quantobj -> cmap[0].red = 0;
- quantobj -> cmap[0].green = 0;
- quantobj -> cmap[0].blue = 0;
- quantobj -> cmap[1].red = 255;
- quantobj -> cmap[1].green = 255;
- quantobj -> cmap[1].blue = 255;
- }
- static void
- webpal_pass1 (QuantizeObj *quantobj)
- {
- int i;
- quantobj -> actual_number_of_colors = 216;
- for (i=0;i<216;i++)
- {
- quantobj->cmap[i].red = webpal[i*3];
- quantobj->cmap[i].green = webpal[i*3 +1];
- quantobj->cmap[i].blue = webpal[i*3 +2];
- }
- }
- static void
- custompal_pass1 (QuantizeObj *quantobj)
- {
- int i;
- GSList *list;
- PaletteEntry *entry;
-
- /* fprintf(stderr, "custompal_pass1: using (theCustomPalette %s) from (file %s)\n",
- theCustomPalette->name, theCustomPalette->filename); */
-
- for (i=0,list=theCustomPalette->colors;
- list;
- i++,list=g_slist_next(list))
- {
- entry = (PaletteEntry *) list->data;
- quantobj->cmap[i].red = entry->color[0];
- quantobj->cmap[i].green = entry->color[1];
- quantobj->cmap[i].blue = entry->color[2];
- }
- quantobj -> actual_number_of_colors = i;
- }
-
- /*
- * Map some rows of pixels to the output colormapped representation.
- */
-
- static void
- median_cut_pass2_no_dither_gray (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq * cachep;
- unsigned char *src, *dest;
- int row, col;
- int pixel;
- int has_alpha;
- unsigned long* index_used_count = quantobj->index_used_count;
- int alpha_dither = quantobj->want_alpha_dither;
- int offsetx, offsety;
- void *pr;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- for (row = 0; row < srcPR.h; row++)
- {
- for (col = 0; col < srcPR.w; col++)
- {
- /* get pixel value and index into the cache */
- pixel = src[GRAY_PIX];
- cachep = &histogram[pixel];
- /* If we have not seen this color before, find nearest colormap entry */
- /* and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_gray (quantobj, histogram, pixel);
-
- if (has_alpha)
- {
- if ((dest[ALPHA_I_PIX] =
- (
- (alpha_dither ?
- ((src[ALPHA_G_PIX] << 6) > (255 * DM[(col+offsetx+srcPR.x)&DM_WIDTHMASK][(row+offsety+srcPR.y)&DM_HEIGHTMASK])) :
- (src[ALPHA_G_PIX] > 127)
- ) ? 255 : 0)))
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
- }
- else
- {
- /* Now emit the colormap index for this cell */
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
- }
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
- }
-
- static void
- median_cut_pass2_fixed_dither_gray (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq* cachep;
- Color* color;
- unsigned char *src, *dest;
- int row, col;
- int pixel;
- int re, R;
- unsigned long* index_used_count = quantobj->index_used_count;
- int has_alpha;
- int alpha_dither = quantobj->want_alpha_dither;
- int offsetx, offsety;
- void *pr;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- for (row = 0; row < srcPR.h; row++)
- {
- for (col = 0; col < srcPR.w; col++)
- {
- int dmval =
- DM[(col+offsetx+srcPR.x)&DM_WIDTHMASK]
- [(row+offsety+srcPR.y)&DM_HEIGHTMASK];
-
- /* get pixel value and index into the cache */
- pixel = src[GRAY_PIX];
- cachep = &histogram[pixel];
- /* If we have not seen this color before, find nearest colormap entry */
- /* and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_gray (quantobj, histogram, pixel);
-
- color = &quantobj->cmap[*cachep - 1];
- re = src[GRAY_PIX] - color->red;
- re = (re * dmval * 2) / 63;
- R = (CLAMP0255(color->red + re));
-
- cachep = &histogram[R];
- /* If we have not seen this color before, find nearest
- colormap entry and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_gray (quantobj, histogram, R);
-
- if (has_alpha)
- {
- if ((dest[ALPHA_I_PIX] =
- ((alpha_dither ?
- ((src[ALPHA_G_PIX] << 6) > (255 * dmval)) :
- (src[ALPHA_G_PIX] > 127)
- ) ? 255 : 0)))
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
- }
- else
- {
- /* Now emit the colormap index for this cell, barfbarf */
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
- }
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
- }
-
- static void
- median_cut_pass2_no_dither_rgb (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq * cachep;
- unsigned char *src, *dest;
- int R, G, B;
- int row, col;
- int has_alpha;
- void *pr;
- int red_pix = RED_PIX;
- int green_pix = GREEN_PIX;
- int blue_pix = BLUE_PIX;
- int alpha_pix = ALPHA_PIX;
- int alpha_dither = quantobj->want_alpha_dither;
- int offsetx, offsety;
- unsigned long* index_used_count = quantobj->index_used_count;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- /* In the case of web/mono palettes, we actually force
- * grayscale drawables through the rgb pass2 functions
- */
- if (drawable_gray (GIMP_DRAWABLE(layer)))
- red_pix = green_pix = blue_pix = GRAY_PIX;
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- for (row = 0; row < srcPR.h; row++)
- {
- for (col = 0; col < srcPR.w; col++)
- {
- if (has_alpha)
- {
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[alpha_pix] << 6) > (255 * DM[(col+offsetx+srcPR.x)&DM_WIDTHMASK][(row+offsety+srcPR.y)&DM_HEIGHTMASK])) :
- (src[alpha_pix] > 127)
- ) ? 255 : 0)
- == 0)
- {
- goto next_pixel;
- }
- }
-
- /* get pixel value and index into the cache */
- R = (src[red_pix]) >> R_SHIFT;
- G = (src[green_pix]) >> G_SHIFT;
- B = (src[blue_pix]) >> B_SHIFT;
- cachep = &histogram[R*MR + G*MG + B];
- /* If we have not seen this color before, find nearest
- colormap entry and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_rgb (quantobj, histogram, R, G, B);
-
- /* Now emit the colormap index for this cell, barfbarf */
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
-
- next_pixel:
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
- }
-
- static void
- median_cut_pass2_fixed_dither_rgb (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq* cachep;
- Color* color;
- unsigned char *src, *dest;
- int R, G, B;
- int row, col;
- int has_alpha;
- int re, ge, be;
- void* pr;
- int red_pix = RED_PIX;
- int green_pix = GREEN_PIX;
- int blue_pix = BLUE_PIX;
- int alpha_pix = ALPHA_PIX;
- int alpha_dither = quantobj->want_alpha_dither;
- int offsetx, offsety;
- unsigned long* index_used_count = quantobj->index_used_count;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- /* In the case of web/mono palettes, we actually force
- * grayscale drawables through the rgb pass2 functions
- */
- if (drawable_gray (GIMP_DRAWABLE(layer)))
- red_pix = green_pix = blue_pix = GRAY_PIX;
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- for (row = 0; row < srcPR.h; row++)
- {
- for (col = 0; col < srcPR.w; col++)
- {
- int dmval =
- DM[(col+offsetx+srcPR.x)&DM_WIDTHMASK]
- [(row+offsety+srcPR.y)&DM_HEIGHTMASK];
-
- if (has_alpha)
- {
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[alpha_pix] << 6) > (255 * dmval)) :
- (src[alpha_pix] > 127)
- ) ? 255 : 0)
- == 0)
- {
- goto next_pixel;
- }
- }
-
- /* get pixel value and index into the cache */
- R = (src[red_pix]) >> R_SHIFT;
- G = (src[green_pix]) >> G_SHIFT;
- B = (src[blue_pix]) >> B_SHIFT;
- cachep = &histogram[R*MR + G*MG + B];
- /* If we have not seen this color before, find nearest
- colormap entry and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_rgb (quantobj, histogram, R, G, B);
-
- /* Get the error and modulate it between 0x and 2x according
- to the fixed dither matrix, then add it back to the 0x colour
- and look up the new histogram entry. To do better fixed
- dithering, I believe that we need to be able to find the
- closest colour match on the 'other side' of the desired colour,
- which is not information which we have cheap access to. */
- color = &quantobj->cmap[*cachep - 1];
- re = src[red_pix] - color->red;
- ge = src[green_pix] - color->green;
- be = src[blue_pix] - color->blue;
-
- re = (re * dmval * 2) / 63;
- ge = (ge * dmval * 2) / 63;
- be = (be * dmval * 2) / 63;
-
- R = (CLAMP0255(color->red + re)) >> R_SHIFT;
- G = (CLAMP0255(color->green + ge)) >> G_SHIFT;
- B = (CLAMP0255(color->blue + be)) >> B_SHIFT;
-
- cachep = &histogram[R*MR + G*MG + B];
- /* If we have not seen this color before, find nearest
- colormap entry and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_rgb (quantobj, histogram, R, G, B);
-
- /* Now emit the colormap index for this cell, barfbarf */
- index_used_count[dest[INDEXED_PIX] = *cachep - 1]++;
-
- next_pixel:
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
- }
-
- static void
- median_cut_pass2_nodestruct_dither_rgb (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- unsigned char *src, *dest;
- int row, col;
- int has_alpha;
- int alpha_dither = quantobj->want_alpha_dither;
- void *pr;
- int red_pix = RED_PIX;
- int green_pix = GREEN_PIX;
- int blue_pix = BLUE_PIX;
- int alpha_pix = ALPHA_PIX;
- int i;
- int lastindex = 0;
- int lastred = -1;
- int lastgreen = -1;
- int lastblue = -1;
- int offsetx, offsety;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- for (pr = pixel_regions_register (2, &srcPR, &destPR); pr != NULL; pr = pixel_regions_process (pr))
- {
- src = srcPR.data;
- dest = destPR.data;
- for (row = 0; row < srcPR.h; row++)
- {
- for (col = 0; col < srcPR.w; col++)
- {
- if ((has_alpha && (alpha_dither ?
- ((src[alpha_pix] << 6) > (255 * DM[(col+srcPR.x+offsetx)&DM_WIDTHMASK][(row+srcPR.y+offsety)&DM_HEIGHTMASK])) :
- (src[alpha_pix] > 127)))
- || !has_alpha)
- {
- if ((lastred == src[red_pix]) &&
- (lastgreen == src[green_pix]) &&
- (lastblue == src[blue_pix]))
- {
- /* same pixel colour as last time */
- dest[INDEXED_PIX] = lastindex;
- if (has_alpha)
- dest[ALPHA_I_PIX] = 255;
- }
- else
- {
- for (i = 0 ;
- i < quantobj->actual_number_of_colors;
- i++)
- {
- if (
- (quantobj->cmap[i].red == src[red_pix]) &&
- (quantobj->cmap[i].green == src[green_pix]) &&
- (quantobj->cmap[i].blue == src[blue_pix])
- )
- {
- lastred = src[red_pix];
- lastgreen = src[green_pix];
- lastblue = src[blue_pix];
- lastindex = i;
- goto got_colour;
- }
- }
- g_error ("Non-existant colour was expected to "
- "be in non-destructive colourmap.");
- got_colour:
- dest[INDEXED_PIX] = lastindex;
- if (has_alpha)
- dest[ALPHA_I_PIX] = 255;
- }
- }
- else
- { /* have alpha, and transparent */
- dest[ALPHA_I_PIX] = 0;
- }
-
- src += srcPR.bytes;
- dest += destPR.bytes;
- }
- }
- }
- }
-
-
- /*
- * Initialize the error-limiting transfer function (lookup table).
- * The raw F-S error computation can potentially compute error values of up to
- * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
- * much less, otherwise obviously wrong pixels will be created. (Typical
- * effects include weird fringes at color-area boundaries, isolated bright
- * pixels in a dark area, etc.) The standard advice for avoiding this problem
- * is to ensure that the "corners" of the color cube are allocated as output
- * colors; then repeated errors in the same direction cannot cause cascading
- * error buildup. However, that only prevents the error from getting
- * completely out of hand; Aaron Giles reports that error limiting improves
- * the results even with corner colors allocated.
- * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
- * well, but the smoother transfer function used below is even better. Thanks
- * to Aaron Giles for this idea.
- */
-
- static int *
- init_error_limit (const int error_freedom)
- /* Allocate and fill in the error_limiter table */
- {
- int *table;
- int in, out;
-
- /* #define STEPSIZE 16 */
- /* #define STEPSIZE 200 */
-
- table = g_malloc (sizeof (int) * (255 * 2 + 1));
- table += 255; /* so we can index -255 ... +255 */
-
- if (error_freedom == 0)
- {
- /* Coarse function, much bleeding. */
-
- const int STEPSIZE = 190;
-
- for (in = 0; in < STEPSIZE; in++)
- {
- table[in] = in;
- table[-in] = -in;
- }
- for (; in <= 255; in++)
- {
- table[in] = STEPSIZE;
- table[-in] = -STEPSIZE;
- }
- return (table);
- }
- else
- {
- /* Smooth function, bleeding more constrained */
-
- const int STEPSIZE = 24;
-
- /* Map errors 1:1 up to +- STEPSIZE */
- out = 0;
- for (in = 0; in < STEPSIZE; in++, out++)
- {
- table[in] = out;
- table[-in] = -out;
- }
-
- /* Map errors 1:2 up to +- 3*STEPSIZE */
- for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1)
- {
- table[in] = out;
- table[-in] = -out;
- }
-
- /* Clamp the rest to final out value (which is STEPSIZE*2) */
- for (; in <= 255; in++)
- {
- table[in] = out;
- table[-in] = -out;
- }
-
- return table;
- }
- }
-
-
- /*
- * Map some rows of pixels to the output colormapped representation.
- * Perform floyd-steinberg dithering.
- */
-
- static void
- median_cut_pass2_fs_dither_gray (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq *cachep;
- Color *color;
- int *error_limiter;
- const short *fs_err1, *fs_err2;
- const short *fs_err3, *fs_err4;
- const short *range_limiter;
- int src_bytes, dest_bytes;
- unsigned char *src, *dest;
- unsigned char *src_buf, *dest_buf;
- int *next_row, *prev_row;
- int *nr, *pr;
- int *tmp;
- int pixel;
- int pixele;
- int row, col;
- int index;
- int step_dest, step_src;
- int odd_row;
- int has_alpha;
- int offsetx, offsety;
- int alpha_dither = quantobj->want_alpha_dither;
- int width, height;
- unsigned long* index_used_count = quantobj->index_used_count;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- src_bytes = GIMP_DRAWABLE(layer)->bytes;
- dest_bytes = new_tiles->bpp;
- width = GIMP_DRAWABLE(layer)->width;
- height = GIMP_DRAWABLE(layer)->height;
-
- error_limiter = init_error_limit (quantobj->error_freedom);
- range_limiter = range_array + 256;
-
- src_buf = g_malloc (width * src_bytes);
- dest_buf = g_malloc (width * dest_bytes);
- next_row = g_malloc (sizeof (int) * (width + 2));
- prev_row = g_malloc (sizeof (int) * (width + 2));
-
- memset (prev_row, 0, (width + 2) * sizeof (int));
-
- fs_err1 = floyd_steinberg_error1 + 511;
- fs_err2 = floyd_steinberg_error2 + 511;
- fs_err3 = floyd_steinberg_error3 + 511;
- fs_err4 = floyd_steinberg_error4 + 511;
-
- odd_row = 0;
-
- for (row = 0; row < height; row++)
- {
- pixel_region_get_row (&srcPR, 0, row, width, src_buf, 1);
-
- src = src_buf;
- dest = dest_buf;
-
- nr = next_row;
- pr = prev_row + 1;
-
- if (odd_row)
- {
- step_dest = -dest_bytes;
- step_src = -src_bytes;
-
- src += (width * src_bytes) - src_bytes;
- dest += (width * dest_bytes) - dest_bytes;
-
- nr += width + 1;
- pr += width;
-
- *(nr - 1) = 0;
- }
- else
- {
- step_dest = dest_bytes;
- step_src = src_bytes;
-
- *(nr + 1) = 0;
- }
-
- *nr = 0;
-
- for (col = 0; col < width; col++)
- {
- pixel = range_limiter[src[GRAY_PIX] + error_limiter[*pr]];
-
- cachep = &histogram[pixel];
- /* If we have not seen this color before, find nearest colormap entry */
- /* and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_gray (quantobj, histogram, pixel);
-
- if (has_alpha)
- {
- if (odd_row)
- {
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[ALPHA_G_PIX] << 6) > (255 * DM[((width-col)+offsetx-1)&DM_WIDTHMASK][(row+offsety)&DM_HEIGHTMASK])) :
- (src[ALPHA_G_PIX] > 127)
- ) ? 255 : 0)
- == 0)
- {
- pr--;
- nr--;
- *(nr - 1) = 0;
- goto next_pixel;
- }
- }
- else
- {
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[ALPHA_G_PIX] << 6) > (255 * DM[(col+offsetx)&DM_WIDTHMASK][(row+offsety)&DM_HEIGHTMASK])) :
- (src[ALPHA_G_PIX] > 127)
- ) ? 255 : 0)
- == 0)
- {
- pr++;
- nr++;
- *(nr + 1) = 0;
- goto next_pixel;
- }
- }
- }
-
- index = *cachep - 1;
- index_used_count[dest[INDEXED_PIX] = index]++;
-
- color = &quantobj->cmap[index];
- pixele = pixel - color->red;
-
- if (odd_row)
- {
- *(--pr) += fs_err1[pixele];
- *nr-- += fs_err2[pixele];
- *nr += fs_err3[pixele];
- *(nr-1) = fs_err4[pixele];
- }
- else
- {
- *(++pr) += fs_err1[pixele];
- *nr++ += fs_err2[pixele];
- *nr += fs_err3[pixele];
- *(nr+1) = fs_err4[pixele];
- }
-
- next_pixel:
-
- dest += step_dest;
- src += step_src;
- }
-
- tmp = next_row;
- next_row = prev_row;
- prev_row = tmp;
-
- odd_row = !odd_row;
-
- pixel_region_set_row (&destPR, 0, row, width, dest_buf);
- }
-
- g_free (error_limiter - 255); /* good lord. */
- g_free (next_row);
- g_free (prev_row);
- g_free (src_buf);
- g_free (dest_buf);
- }
-
- static void
- median_cut_pass2_rgb_init (QuantizeObj *quantobj)
- {
- zero_histogram_rgb (quantobj->histogram);
-
- /* Mark all indices as currently unused */
- memset (quantobj->index_used_count, 0, 256 * sizeof(unsigned long));
- }
-
- static void
- median_cut_pass2_gray_init (QuantizeObj *quantobj)
- {
- zero_histogram_gray (quantobj->histogram);
-
- /* Mark all indices as currently unused */
- memset (quantobj->index_used_count, 0, 256 * sizeof(unsigned long));
- }
-
- static void
- median_cut_pass2_fs_dither_rgb (QuantizeObj *quantobj,
- Layer *layer,
- TileManager *new_tiles)
- {
- PixelRegion srcPR, destPR;
- CFHistogram histogram = quantobj->histogram;
- ColorFreq *cachep;
- Color *color;
- int *error_limiter;
- const short *fs_err1, *fs_err2;
- const short *fs_err3, *fs_err4;
- const short *range_limiter;
- int src_bytes, dest_bytes;
- unsigned char *src, *dest;
- unsigned char *src_buf, *dest_buf;
- int *red_n_row, *red_p_row;
- int *grn_n_row, *grn_p_row;
- int *blu_n_row, *blu_p_row;
- int *rnr, *rpr;
- int *gnr, *gpr;
- int *bnr, *bpr;
- int *tmp;
- int r, g, b;
- int re, ge, be;
- int row, col;
- int index;
- int step_dest, step_src;
- int odd_row;
- int has_alpha;
- int width, height;
- int red_pix = RED_PIX;
- int green_pix = GREEN_PIX;
- int blue_pix = BLUE_PIX;
- int alpha_pix = ALPHA_PIX;
- int offsetx, offsety;
- int alpha_dither = quantobj->want_alpha_dither;
- unsigned long *index_used_count = quantobj->index_used_count;
-
- drawable_offsets (GIMP_DRAWABLE(layer), &offsetx, &offsety);
-
- /* In the case of web/mono palettes, we actually force
- * grayscale drawables through the rgb pass2 functions
- */
- if (drawable_gray (GIMP_DRAWABLE(layer)))
- red_pix = green_pix = blue_pix = GRAY_PIX;
-
- has_alpha = layer_has_alpha (layer);
- pixel_region_init (&srcPR, GIMP_DRAWABLE(layer)->tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, FALSE);
- pixel_region_init (&destPR, new_tiles, 0, 0, GIMP_DRAWABLE(layer)->width, GIMP_DRAWABLE(layer)->height, TRUE);
- src_bytes = GIMP_DRAWABLE(layer)->bytes;
- dest_bytes = new_tiles->bpp;
- width = GIMP_DRAWABLE(layer)->width;
- height = GIMP_DRAWABLE(layer)->height;
-
- error_limiter = init_error_limit (quantobj->error_freedom);
- range_limiter = range_array + 256;
-
- src_buf = g_malloc (width * src_bytes);
- dest_buf = g_malloc (width * dest_bytes);
- red_n_row = g_malloc (sizeof (int) * (width + 2));
- red_p_row = g_malloc (sizeof (int) * (width + 2));
- grn_n_row = g_malloc (sizeof (int) * (width + 2));
- grn_p_row = g_malloc (sizeof (int) * (width + 2));
- blu_n_row = g_malloc (sizeof (int) * (width + 2));
- blu_p_row = g_malloc (sizeof (int) * (width + 2));
-
- memset (red_p_row, 0, (width + 2) * sizeof (int));
- memset (grn_p_row, 0, (width + 2) * sizeof (int));
- memset (blu_p_row, 0, (width + 2) * sizeof (int));
-
- fs_err1 = floyd_steinberg_error1 + 511;
- fs_err2 = floyd_steinberg_error2 + 511;
- fs_err3 = floyd_steinberg_error3 + 511;
- fs_err4 = floyd_steinberg_error4 + 511;
-
- odd_row = 0;
-
- for (row = 0; row < height; row++)
- {
- pixel_region_get_row (&srcPR, 0, row, width, src_buf, 1);
-
- src = src_buf;
- dest = dest_buf;
-
- rnr = red_n_row;
- gnr = grn_n_row;
- bnr = blu_n_row;
- rpr = red_p_row + 1;
- gpr = grn_p_row + 1;
- bpr = blu_p_row + 1;
-
- if (odd_row)
- {
- step_dest = -dest_bytes;
- step_src = -src_bytes;
-
- src += (width * src_bytes) - src_bytes;
- dest += (width * dest_bytes) - dest_bytes;
-
- rnr += width + 1;
- gnr += width + 1;
- bnr += width + 1;
- rpr += width;
- gpr += width;
- bpr += width;
-
- *(rnr - 1) = *(gnr - 1) = *(bnr - 1) = 0;
- }
- else
- {
- step_dest = dest_bytes;
- step_src = src_bytes;
-
- *(rnr + 1) = *(gnr + 1) = *(bnr + 1) = 0;
- }
-
- *rnr = *gnr = *bnr = 0;
-
- for (col = 0; col < width; col++)
- {
- if (has_alpha)
- {
- if (odd_row)
- {
- /* I get goosebumps over this expression. */
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[alpha_pix] << 6) > (255 * DM[((width-col)+offsetx-1)&DM_WIDTHMASK][(row+offsety)&DM_HEIGHTMASK])) :
- (src[alpha_pix] > 127)
- ) ? 255 : 0)
- == 0)
- {
- rpr--; gpr--; bpr--;
- rnr--; gnr--; bnr--;
- *(rnr - 1) = *(gnr - 1) = *(bnr - 1) = 0;
- goto next_pixel;
- }
- }
- else
- {
- if ((dest[ALPHA_I_PIX] =
- (alpha_dither ?
- ((src[alpha_pix] << 6) > (255 * DM[(col+offsetx)&DM_WIDTHMASK][(row+offsety)&DM_HEIGHTMASK])) :
- (src[alpha_pix] > 127)
- ) ? 255 : 0)
- == 0)
- {
- rpr++; gpr++; bpr++;
- rnr++; gnr++; bnr++;
- *(rnr + 1) = *(gnr + 1) = *(bnr + 1) = 0;
- goto next_pixel;
- }
- }
- }
-
- r = range_limiter[src[red_pix] + error_limiter[*rpr]];
- g = range_limiter[src[green_pix] + error_limiter[*gpr]];
- b = range_limiter[src[blue_pix] + error_limiter[*bpr]];
-
- re = r >> R_SHIFT;
- ge = g >> G_SHIFT;
- be = b >> B_SHIFT;
-
- cachep = &histogram[re*MR + ge*MG + be];
- /* If we have not seen this color before, find nearest
- colormap entry and update the cache */
- if (*cachep == 0)
- fill_inverse_cmap_rgb (quantobj, histogram, re, ge, be);
-
- index = *cachep - 1;
- index_used_count[index]++;
- dest[INDEXED_PIX] = index;
-
- color = &quantobj->cmap[index];
- re = r - color->red;
- ge = g - color->green;
- be = b - color->blue;
-
- if (odd_row)
- {
- *(--rpr) += fs_err1[re];
- *(--gpr) += fs_err1[ge];
- *(--bpr) += fs_err1[be];
-
- *rnr-- += fs_err2[re];
- *gnr-- += fs_err2[ge];
- *bnr-- += fs_err2[be];
-
- *rnr += fs_err3[re];
- *gnr += fs_err3[ge];
- *bnr += fs_err3[be];
-
- *(rnr-1) = fs_err4[re];
- *(gnr-1) = fs_err4[ge];
- *(bnr-1) = fs_err4[be];
- }
- else
- {
- *(++rpr) += fs_err1[re];
- *(++gpr) += fs_err1[ge];
- *(++bpr) += fs_err1[be];
-
- *rnr++ += fs_err2[re];
- *gnr++ += fs_err2[ge];
- *bnr++ += fs_err2[be];
-
- *rnr += fs_err3[re];
- *gnr += fs_err3[ge];
- *bnr += fs_err3[be];
-
- *(rnr+1) = fs_err4[re];
- *(gnr+1) = fs_err4[ge];
- *(bnr+1) = fs_err4[be];
- }
-
- next_pixel:
-
- dest += step_dest;
- src += step_src;
- }
-
- tmp = red_n_row;
- red_n_row = red_p_row;
- red_p_row = tmp;
-
- tmp = grn_n_row;
- grn_n_row = grn_p_row;
- grn_p_row = tmp;
-
- tmp = blu_n_row;
- blu_n_row = blu_p_row;
- blu_p_row = tmp;
-
- odd_row = !odd_row;
-
- pixel_region_set_row (&destPR, 0, row, width, dest_buf);
- }
-
- g_free (error_limiter - 255);
- g_free (red_n_row);
- g_free (red_p_row);
- g_free (grn_n_row);
- g_free (grn_p_row);
- g_free (blu_n_row);
- g_free (blu_p_row);
- g_free (src_buf);
- g_free (dest_buf);
- }
-
-
- static void
- delete_median_cut (QuantizeObj *quantobj)
- {
- g_free (quantobj->histogram);
- g_free (quantobj);
- }
-
-
- /**************************************************************/
-
-
- static QuantizeObj*
- initialize_median_cut (int type,
- int num_colors,
- ConvertDitherType dither_type,
- ConvertPaletteType palette_type,
- int want_alpha_dither)
- {
- QuantizeObj * quantobj;
-
- /* Initialize the data structures */
- quantobj = g_malloc (sizeof (QuantizeObj));
-
- if (type == GRAY && palette_type == MAKE_PALETTE)
- quantobj->histogram = g_malloc (sizeof (ColorFreq) * 256);
- else
- quantobj->histogram = g_malloc (sizeof (ColorFreq) *
- HIST_R_ELEMS *
- HIST_G_ELEMS *
- HIST_B_ELEMS);
-
- quantobj->desired_number_of_colors = num_colors;
- quantobj->want_alpha_dither = want_alpha_dither;
-
- switch (type)
- {
- case GRAY:
- switch (palette_type)
- {
- case MAKE_PALETTE:
- quantobj->first_pass = median_cut_pass1_gray;
- break;
- case WEB_PALETTE:
- quantobj->first_pass = webpal_pass1;
- break;
- case CUSTOM_PALETTE:
- quantobj->first_pass = custompal_pass1;
- needs_quantize=TRUE;
- break;
- case MONO_PALETTE:
- default:
- quantobj->first_pass = monopal_pass1;
- }
- if (palette_type == WEB_PALETTE ||
- palette_type == MONO_PALETTE || palette_type == CUSTOM_PALETTE)
- switch (dither_type)
- {
- case NODESTRUCT_DITHER:
- default:
- g_warning("Uh-oh, bad dither type, W1");
- case NO_DITHER:
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_no_dither_rgb;
- break;
- case FS_DITHER:
- quantobj->error_freedom = 0;
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_rgb;
- break;
- case FSLOWBLEED_DITHER:
- quantobj->error_freedom = 1;
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_rgb;
- break;
- case FIXED_DITHER:
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fixed_dither_rgb;
- break;
- }
- else
- switch (dither_type)
- {
- case NODESTRUCT_DITHER:
- default:
- g_warning("Uh-oh, bad dither type, W2");
- case NO_DITHER:
- quantobj->second_pass_init = median_cut_pass2_gray_init;
- quantobj->second_pass = median_cut_pass2_no_dither_gray;
- break;
- case FS_DITHER:
- quantobj->error_freedom = 0;
- quantobj->second_pass_init = median_cut_pass2_gray_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_gray;
- break;
- case FSLOWBLEED_DITHER:
- quantobj->error_freedom = 1;
- quantobj->second_pass_init = median_cut_pass2_gray_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_gray;
- break;
- case FIXED_DITHER:
- quantobj->second_pass_init = median_cut_pass2_gray_init;
- quantobj->second_pass = median_cut_pass2_fixed_dither_gray;
- break;
- }
- break;
- case RGB:
- switch (palette_type)
- {
- case MAKE_PALETTE:
- quantobj->first_pass = median_cut_pass1_rgb;
- break;
- case WEB_PALETTE:
- quantobj->first_pass = webpal_pass1;
- needs_quantize=TRUE;
- break;
- case CUSTOM_PALETTE:
- quantobj->first_pass = custompal_pass1;
- needs_quantize=TRUE;
- break;
- case MONO_PALETTE:
- default:
- quantobj->first_pass = monopal_pass1;
- }
- switch (dither_type)
- {
- case NO_DITHER:
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_no_dither_rgb;
- break;
- case FS_DITHER:
- quantobj->error_freedom = 0;
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_rgb;
- break;
- case FSLOWBLEED_DITHER:
- quantobj->error_freedom = 1;
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fs_dither_rgb;
- break;
- case NODESTRUCT_DITHER:
- quantobj->second_pass_init = NULL;
- quantobj->second_pass = median_cut_pass2_nodestruct_dither_rgb;
- break;
- case FIXED_DITHER:
- quantobj->second_pass_init = median_cut_pass2_rgb_init;
- quantobj->second_pass = median_cut_pass2_fixed_dither_rgb;
- break;
- }
- break;
- }
- quantobj->delete_func = delete_median_cut;
-
- return quantobj;
- }
-