The Independent JPEG Group's JPEG software v5a
diff --git a/jquant1.c b/jquant1.c
index a68f3e7..9a9e63a 100644
--- a/jquant1.c
+++ b/jquant1.c
@@ -52,7 +52,7 @@
/* Declarations for ordered dithering.
*
- * We use a standard 4x4 ordered dither array. The basic concept of ordered
+ * We use a standard 16x16 ordered dither array. The basic concept of ordered
* dithering is described in many references, for instance Dale Schumacher's
* chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991).
* In place of Schumacher's comparisons against a "threshold" value, we add a
@@ -68,11 +68,36 @@
* table in both directions.
*/
-#define ODITHER_SIZE 4 /* dimension of dither matrix */
-#define ODITHER_CELLS (4*4) /* number of cells in dither matrix */
-#define ODITHER_MASK 3 /* mask for wrapping around dither counters */
+#define ODITHER_SIZE 16 /* dimension of dither matrix */
+/* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */
+#define ODITHER_CELLS (ODITHER_SIZE*ODITHER_SIZE) /* # cells in matrix */
+#define ODITHER_MASK (ODITHER_SIZE-1) /* mask for wrapping around counters */
typedef int ODITHER_MATRIX[ODITHER_SIZE][ODITHER_SIZE];
+typedef int (*ODITHER_MATRIX_PTR)[ODITHER_SIZE];
+
+static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = {
+ /* Bayer's order-4 dither array. Generated by the code given in
+ * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I.
+ * The values in this array must range from 0 to ODITHER_CELLS-1.
+ */
+ 0,192, 48,240, 12,204, 60,252, 3,195, 51,243, 15,207, 63,255,
+ 128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127,
+ 32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223,
+ 160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95,
+ 8,200, 56,248, 4,196, 52,244, 11,203, 59,251, 7,199, 55,247,
+ 136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119,
+ 40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215,
+ 168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87,
+ 2,194, 50,242, 14,206, 62,254, 1,193, 49,241, 13,205, 61,253,
+ 130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125,
+ 34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221,
+ 162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93,
+ 10,202, 58,250, 6,198, 54,246, 9,201, 57,249, 5,197, 53,245,
+ 138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117,
+ 42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213,
+ 170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85
+};
/* Declarations for Floyd-Steinberg dithering.
@@ -125,7 +150,7 @@
/* Variables for ordered dithering */
int row_index; /* cur row's vertical index in dither matrix */
- ODITHER_MATRIX *odither; /* one dither array per component */
+ ODITHER_MATRIX_PTR odither[MAX_Q_COMPS]; /* one dither array per component */
/* Variables for Floyd-Steinberg dithering */
FSERRPTR fserrors[MAX_Q_COMPS]; /* accumulated errors */
@@ -227,6 +252,41 @@
/*
+ * Create an ordered-dither array for a component having ncolors
+ * distinct output values.
+ */
+
+LOCAL ODITHER_MATRIX_PTR
+make_odither_array (j_decompress_ptr cinfo, int ncolors)
+{
+ ODITHER_MATRIX_PTR odither;
+ int j,k;
+ INT32 num,den;
+
+ odither = (ODITHER_MATRIX_PTR)
+ (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
+ SIZEOF(ODITHER_MATRIX));
+ /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1).
+ * Hence the dither value for the matrix cell with fill order f
+ * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1).
+ * On 16-bit-int machine, be careful to avoid overflow.
+ */
+ den = 2 * ODITHER_CELLS * ((INT32) (ncolors - 1));
+ for (j = 0; j < ODITHER_SIZE; j++) {
+ for (k = 0; k < ODITHER_SIZE; k++) {
+ num = ((INT32) (ODITHER_CELLS-1 - 2*((int)base_dither_matrix[j][k])))
+ * MAXJSAMPLE;
+ /* Ensure round towards zero despite C's lack of consistency
+ * about rounding negative values in integer division...
+ */
+ odither[j][k] = (int) (num<0 ? -((-num)/den) : num/den);
+ }
+ }
+ return odither;
+}
+
+
+/*
* Create the colormap and color index table.
* Also creates the ordered-dither tables, if required.
*/
@@ -239,7 +299,7 @@
JSAMPROW indexptr;
int total_colors; /* Number of distinct output colors */
int Ncolors[MAX_Q_COMPS]; /* # of values alloced to each component */
- ODITHER_MATRIX *odither;
+ ODITHER_MATRIX_PTR odither;
int i,j,k, nci, blksize, blkdist, ptr, val, pad;
/* Select number of colors for each component */
@@ -319,41 +379,21 @@
cinfo->actual_number_of_colors = total_colors;
if (cinfo->dither_mode == JDITHER_ORDERED) {
- /* Allocate and fill in the ordered-dither tables. */
- odither = (ODITHER_MATRIX *)
- (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
- cinfo->out_color_components * SIZEOF(ODITHER_MATRIX));
- cquantize->odither = odither;
+ /* Allocate and fill in the ordered-dither tables. Components having
+ * the same number of representative colors may share a dither table.
+ */
for (i = 0; i < cinfo->out_color_components; i++) {
nci = Ncolors[i]; /* # of distinct values for this color */
- /* The inter-value distance for this color is MAXJSAMPLE/(nci-1).
- * Hence the dither value for the matrix cell with fill order j
- * (j=1..N) should be (N+1-2*j)/(2*(N+1)) * MAXJSAMPLE/(nci-1).
- */
- val = 2 * (ODITHER_CELLS + 1) * (nci - 1); /* denominator */
- /* Macro is coded to ensure round towards zero despite C's
- * lack of consistency in integer division...
- */
-#define ODITHER_DIV(num,den) ((num)<0 ? -((-(num))/(den)) : (num)/(den))
-#define ODITHER_VAL(j) ODITHER_DIV((ODITHER_CELLS+1-2*j)*MAXJSAMPLE, val)
- /* Traditional fill order for 4x4 dither; see Schumacher's figure 4. */
- odither[0][0][0] = ODITHER_VAL(1);
- odither[0][0][1] = ODITHER_VAL(9);
- odither[0][0][2] = ODITHER_VAL(3);
- odither[0][0][3] = ODITHER_VAL(11);
- odither[0][1][0] = ODITHER_VAL(13);
- odither[0][1][1] = ODITHER_VAL(5);
- odither[0][1][2] = ODITHER_VAL(15);
- odither[0][1][3] = ODITHER_VAL(7);
- odither[0][2][0] = ODITHER_VAL(4);
- odither[0][2][1] = ODITHER_VAL(12);
- odither[0][2][2] = ODITHER_VAL(2);
- odither[0][2][3] = ODITHER_VAL(10);
- odither[0][3][0] = ODITHER_VAL(16);
- odither[0][3][1] = ODITHER_VAL(8);
- odither[0][3][2] = ODITHER_VAL(14);
- odither[0][3][3] = ODITHER_VAL(6);
- odither++; /* advance to next matrix */
+ odither = NULL; /* search for matching prior component */
+ for (j = 0; j < i; j++) {
+ if (nci == Ncolors[j]) {
+ odither = cquantize->odither[j];
+ break;
+ }
+ }
+ if (odither == NULL) /* need a new table? */
+ odither = make_odither_array(cinfo, nci);
+ cquantize->odither[i] = odither;
}
}
}