1
/* Copyright (C) 2001-2006 Artifex Software, Inc.
4
This software is provided AS-IS with no warranty, either express or
7
This software is distributed under license and may not be copied, modified
8
or distributed except as expressly authorized under the terms of that
9
license. Refer to licensing information at http://www.artifex.com/
10
or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
11
San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
14
/* $Id: gsbitops.c 8022 2007-06-05 22:23:38Z giles $ */
15
/* Bitmap filling, copying, and transforming operations */
26
/* ---------------- Bit-oriented operations ---------------- */
28
/* Define masks for little-endian operation. */
29
/* masks[i] has the first i bits off and the rest on. */
30
#if !arch_is_big_endian
31
const bits16 mono_copy_masks[17] = {
32
0xffff, 0xff7f, 0xff3f, 0xff1f,
33
0xff0f, 0xff07, 0xff03, 0xff01,
34
0xff00, 0x7f00, 0x3f00, 0x1f00,
35
0x0f00, 0x0700, 0x0300, 0x0100,
38
const bits32 mono_fill_masks[33] = {
40
((~0xff | (0xff >> (n & 7))) << (n & -8))
41
mask( 0),mask( 1),mask( 2),mask( 3),mask( 4),mask( 5),mask( 6),mask( 7),
42
mask( 8),mask( 9),mask(10),mask(11),mask(12),mask(13),mask(14),mask(15),
43
mask(16),mask(17),mask(18),mask(19),mask(20),mask(21),mask(22),mask(23),
44
mask(24),mask(25),mask(26),mask(27),mask(28),mask(29),mask(30),mask(31),
50
/* Fill a rectangle of bits with an 8x1 pattern. */
51
/* The pattern argument must consist of the pattern in every byte, */
52
/* e.g., if the desired pattern is 0xaa, the pattern argument must */
53
/* have the value 0xaaaa (if ints are short) or 0xaaaaaaaa. */
55
#define chunk mono_fill_chunk
57
#define mono_masks mono_fill_masks
59
bits_fill_rectangle(byte * dest, int dest_bit, uint draster,
60
mono_fill_chunk pattern, int width_bits, int height)
64
int line_count = height;
68
#define FOR_EACH_LINE(stat)\
69
do { stat } while ( inc_ptr(ptr, draster), --line_count )
71
dest += (dest_bit >> 3) & -chunk_align_bytes;
73
bit = dest_bit & chunk_align_bit_mask;
74
last_bit = width_bits + bit - (chunk_bits + 1);
76
if (last_bit < 0) { /* <=1 chunk */
77
set_mono_thin_mask(right_mask, width_bits, bit);
79
FOR_EACH_LINE(*ptr &= ~right_mask;);
80
else if (pattern == (mono_fill_chunk)(-1))
81
FOR_EACH_LINE(*ptr |= right_mask;);
84
*ptr = (*ptr & ~right_mask) | (pattern & right_mask); );
87
int last = last_bit >> chunk_log2_bits;
89
set_mono_left_mask(mask, bit);
90
set_mono_right_mask(right_mask, (last_bit & chunk_bit_mask) + 1);
92
case 0: /* 2 chunks */
94
FOR_EACH_LINE(*ptr &= ~mask; ptr[1] &= ~right_mask;);
95
else if (pattern == (mono_fill_chunk)(-1))
96
FOR_EACH_LINE(*ptr |= mask; ptr[1] |= right_mask;);
99
*ptr = (*ptr & ~mask) | (pattern & mask);
100
ptr[1] = (ptr[1] & ~right_mask) | (pattern & right_mask); );
102
case 1: /* 3 chunks */
104
FOR_EACH_LINE( *ptr &= ~mask;
106
ptr[2] &= ~right_mask; );
107
else if (pattern == (mono_fill_chunk)(-1))
108
FOR_EACH_LINE( *ptr |= mask;
110
ptr[2] |= right_mask; );
112
FOR_EACH_LINE( *ptr = (*ptr & ~mask) | (pattern & mask);
114
ptr[2] = (ptr[2] & ~right_mask) | (pattern & right_mask); );
116
default:{ /* >3 chunks */
117
uint byte_count = (last_bit >> 3) & -chunk_bytes;
120
FOR_EACH_LINE( *ptr &= ~mask;
121
memset(ptr + 1, 0, byte_count);
122
ptr[last + 1] &= ~right_mask; );
123
else if (pattern == (mono_fill_chunk)(-1))
124
FOR_EACH_LINE( *ptr |= mask;
125
memset(ptr + 1, 0xff, byte_count);
126
ptr[last + 1] |= right_mask; );
129
*ptr = (*ptr & ~mask) | (pattern & mask);
130
memset(ptr + 1, (byte) pattern, byte_count);
131
ptr[last + 1] = (ptr[last + 1] & ~right_mask) |
132
(pattern & right_mask); );
140
* Similar to bits_fill_rectangle, but with an additional source mask.
141
* The src_mask variable is 1 for those bits of the original that are
142
* to be retained. The mask argument must consist of the requisite value
143
* in every byte, in the same manner as the pattern.
146
bits_fill_rectangle_masked(byte * dest, int dest_bit, uint draster,
147
mono_fill_chunk pattern, mono_fill_chunk src_mask,
148
int width_bits, int height)
152
int line_count = height;
156
#define FOR_EACH_LINE(stat)\
157
do { stat } while ( inc_ptr(ptr, draster), --line_count )
159
dest += (dest_bit >> 3) & -chunk_align_bytes;
160
ptr = (chunk *) dest;
161
bit = dest_bit & chunk_align_bit_mask;
162
last_bit = width_bits + bit - (chunk_bits + 1);
164
if (last_bit < 0) { /* <=1 chunk */
165
set_mono_thin_mask(right_mask, width_bits, bit);
166
right_mask &= ~src_mask;
168
FOR_EACH_LINE(*ptr &= ~right_mask;);
169
else if (pattern == (mono_fill_chunk)(-1))
170
FOR_EACH_LINE(*ptr |= right_mask;);
173
*ptr = (*ptr & ~right_mask) | (pattern & right_mask); );
176
int last = last_bit >> chunk_log2_bits;
178
set_mono_left_mask(mask, bit);
179
set_mono_right_mask(right_mask, (last_bit & chunk_bit_mask) + 1);
181
right_mask &= ~src_mask;
183
case 0: /* 2 chunks */
185
FOR_EACH_LINE(*ptr &= ~mask; ptr[1] &= ~right_mask;);
186
else if (pattern == (mono_fill_chunk)(-1))
187
FOR_EACH_LINE(*ptr |= mask; ptr[1] |= right_mask;);
190
*ptr = (*ptr & ~mask) | (pattern & mask);
191
ptr[1] = (ptr[1] & ~right_mask) | (pattern & right_mask); );
193
case 1: /* 3 chunks */
195
FOR_EACH_LINE( *ptr &= ~mask;
197
ptr[2] &= ~right_mask; );
198
else if (pattern == (mono_fill_chunk)(-1))
199
FOR_EACH_LINE( *ptr |= mask;
201
ptr[2] |= right_mask; );
203
FOR_EACH_LINE( *ptr = (*ptr & ~mask) | (pattern & mask);
204
ptr[1] =(ptr[1] & src_mask) | pattern;
205
ptr[2] = (ptr[2] & ~right_mask) | (pattern & right_mask); );
207
default:{ /* >3 chunks */
211
FOR_EACH_LINE( *ptr++ &= ~mask;
212
for (i = 0; i < last; i++)
214
*ptr &= ~right_mask; );
215
else if (pattern == (mono_fill_chunk)(-1))
216
FOR_EACH_LINE( *ptr++ |= mask;
217
for (i = 0; i < last; i++)
219
*ptr |= right_mask; );
222
/* note: we know (pattern & ~src_mask) == pattern */
223
*ptr = (*ptr & ~mask) | (pattern & mask);
225
for (i = 0; i < last; i++, ptr++)
226
*ptr = (*ptr & src_mask) | pattern;
227
*ptr = (*ptr & ~right_mask) | (pattern & right_mask); );
234
/* Replicate a bitmap horizontally in place. */
236
bits_replicate_horizontally(byte * data, uint width, uint height,
237
uint raster, uint replicated_width, uint replicated_raster)
239
/* The current algorithm is extremely inefficient! */
240
const byte *orig_row = data + (height - 1) * raster;
241
byte *tile_row = data + (height - 1) * replicated_raster;
245
uint src_bytes = width >> 3;
246
uint dest_bytes = replicated_width >> 3;
248
for (y = height; y-- > 0;
249
orig_row -= raster, tile_row -= replicated_raster
251
uint move = src_bytes;
252
const byte *from = orig_row;
253
byte *to = tile_row + dest_bytes - src_bytes;
255
memmove(to, from, move);
256
while (to - tile_row >= move) {
259
memmove(to, from, move);
263
memmove(tile_row, to, to - tile_row);
267
* This algorithm is inefficient, but probably not worth improving.
269
uint bit_count = width & (uint)(-(int)width); /* lowest bit: 1, 2, or 4 */
270
uint left_mask = (0xff00 >> bit_count) & 0xff;
272
for (y = height; y-- > 0;
273
orig_row -= raster, tile_row -= replicated_raster
277
for (sx = width; sx > 0;) {
281
bits = (orig_row[sx >> 3] << (sx & 7)) & left_mask;
282
for (dx = sx + replicated_width; dx >= width;) {
288
dp = tile_row + (dx >> 3);
289
*dp = (*dp & ~(left_mask >> dbit)) | (bits >> dbit);
296
/* Replicate a bitmap vertically in place. */
298
bits_replicate_vertically(byte * data, uint height, uint raster,
299
uint replicated_height)
302
uint h = replicated_height;
303
uint size = raster * height;
306
memcpy(dest + size, dest, size);
312
/* Find the bounding box of a bitmap. */
313
/* Assume bits beyond the width are zero. */
315
bits_bounding_box(const byte * data, uint height, uint raster,
318
register const ulong *lp;
319
static const byte first_1[16] = {
320
4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
322
static const byte last_1[16] = {
323
0, 4, 3, 4, 2, 4, 3, 4, 1, 4, 3, 4, 2, 4, 3, 4
326
/* Count trailing blank rows. */
327
/* Since the raster is a multiple of sizeof(long), */
328
/* we don't need to scan by bytes, only by longs. */
330
lp = (const ulong *)(data + raster * height);
331
while ((const byte *)lp > data && !lp[-1])
333
if ((const byte *)lp == data) {
334
pbox->p.x = pbox->q.x = pbox->p.y = pbox->q.y = 0;
337
pbox->q.y = height = ((const byte *)lp - data + raster - 1) / raster;
339
/* Count leading blank rows. */
341
lp = (const ulong *)data;
345
uint n = ((const byte *)lp - data) / raster;
349
height -= n, data += n * raster;
352
/* Find the left and right edges. */
353
/* We know that the first and last rows are non-blank. */
356
uint raster_longs = raster >> arch_log2_sizeof_long;
357
uint left = raster_longs - 1, right = 0;
358
ulong llong = 0, rlong = 0;
362
for (q = data, h = height; h-- > 0; q += raster) { /* Work from the left edge by longs. */
363
for (lp = (const ulong *)q, n = 0;
364
n < left && !*lp; lp++, n++
367
left = n, llong = *lp;
370
/* Work from the right edge by longs. */
371
for (lp = (const ulong *)(q + raster - sizeof(long)),
372
n = raster_longs - 1;
374
n > right && !*lp; lp--, n--
377
right = n, rlong = *lp;
382
/* Do binary subdivision on edge longs. We assume that */
383
/* sizeof(long) = 4 or 8. */
384
#if arch_sizeof_long > 8
385
Error_longs_are_too_large();
388
#if arch_is_big_endian
389
# define last_bits(n) ((1L << (n)) - 1)
390
# define shift_out_last(x,n) ((x) >>= (n))
391
# define right_justify_last(x,n) DO_NOTHING
393
# define last_bits(n) (-1L << ((arch_sizeof_long * 8) - (n)))
394
# define shift_out_last(x,n) ((x) <<= (n))
395
# define right_justify_last(x,n) (x) >>= ((arch_sizeof_long * 8) - (n))
398
left <<= arch_log2_sizeof_long + 3;
399
#if arch_sizeof_long == 8
400
if (llong & ~last_bits(32))
401
shift_out_last(llong, 32);
405
if (llong & ~last_bits(16))
406
shift_out_last(llong, 16);
409
if (llong & ~last_bits(8))
410
shift_out_last(llong, 8);
413
right_justify_last(llong, 8);
415
left += first_1[(byte) llong >> 4];
417
left += first_1[(byte) llong] + 4;
419
right <<= arch_log2_sizeof_long + 3;
420
#if arch_sizeof_long == 8
421
if (!(rlong & last_bits(32)))
422
shift_out_last(rlong, 32);
426
if (!(rlong & last_bits(16)))
427
shift_out_last(rlong, 16);
430
if (!(rlong & last_bits(8)))
431
shift_out_last(rlong, 8);
434
right_justify_last(rlong, 8);
436
right += last_1[(byte) rlong >> 4];
438
right += last_1[(uint) rlong & 0xf] + 4;
445
/* Extract a plane from a pixmap. */
447
bits_extract_plane(const bits_plane_t *dest /*write*/,
448
const bits_plane_t *source /*read*/, int shift, int width, int height)
450
int source_depth = source->depth;
451
int source_bit = source->x * source_depth;
452
const byte *source_row = source->data.read + (source_bit >> 3);
453
int dest_depth = dest->depth;
454
uint plane_mask = (1 << dest_depth) - 1;
455
int dest_bit = dest->x * dest_depth;
456
byte *dest_row = dest->data.write + (dest_bit >> 3);
461
} loop_case = EXTRACT_SLOW;
466
/* Check for the fast CMYK cases. */
467
if (!(source_bit | dest_bit)) {
468
switch (source_depth) {
471
(dest_depth == 1 && !(source->raster & 3) &&
472
!(source->x & 1) ? EXTRACT_4_TO_1 :
476
if (dest_depth == 8 && !(shift & 7)) {
477
loop_case = EXTRACT_32_TO_8;
478
source_row += 3 - (shift >> 3);
483
for (y = 0; y < height;
484
++y, source_row += source->raster, dest_row += dest->raster
489
case EXTRACT_4_TO_1: {
490
const byte *source = source_row;
491
byte *dest = dest_row;
493
/* Do groups of 8 pixels. */
494
for (x = width; x >= 8; source += 4, x -= 8) {
496
(*(const bits32 *)source >> shift) & 0x11111111;
499
byte_acegbdfh_to_abcdefgh[(
500
#if arch_is_big_endian
501
(sword >> 21) | (sword >> 14) | (sword >> 7) | sword
503
(sword << 3) | (sword >> 6) | (sword >> 15) | (sword >> 24)
508
/* Do the final 1-7 pixels. */
509
uint test = 0x10 << shift, store = 0x80;
512
*dest = (*source & test ? *dest | store : *dest & ~store);
516
test <<= 4, ++source;
522
case EXTRACT_32_TO_8: {
523
const byte *source = source_row;
524
byte *dest = dest_row;
526
for (x = width; x > 0; source += 4, --x)
531
sample_load_declare_setup(sptr, sbit, source_row, source_bit,
533
sample_store_declare_setup(dptr, dbit, dbbyte, dest_row, dest_bit,
536
sample_store_preload(dbbyte, dptr, dbit, dest_depth);
537
for (x = width; x > 0; --x) {
538
gx_color_index color;
541
sample_load_next_any(color, sptr, sbit, source_depth);
542
pixel = (color >> shift) & plane_mask;
543
sample_store_next8(pixel, dptr, dbit, dest_depth, dbbyte);
545
sample_store_flush(dptr, dbit, dest_depth, dbbyte);
552
/* Expand a plane into a pixmap. */
554
bits_expand_plane(const bits_plane_t *dest /*write*/,
555
const bits_plane_t *source /*read*/, int shift, int width, int height)
558
* Eventually we will optimize this just like bits_extract_plane.
560
int source_depth = source->depth;
561
int source_bit = source->x * source_depth;
562
const byte *source_row = source->data.read + (source_bit >> 3);
563
int dest_depth = dest->depth;
564
int dest_bit = dest->x * dest_depth;
565
byte *dest_row = dest->data.write + (dest_bit >> 3);
570
} loop_case = EXPAND_SLOW;
574
/* Check for the fast CMYK cases. */
575
if (!(source_bit || (dest_bit & 31) || (dest->raster & 3))) {
576
switch (dest_depth) {
578
if (source_depth == 1)
579
loop_case = EXPAND_1_TO_4;
582
if (source_depth == 8 && !(shift & 7))
583
loop_case = EXPAND_8_TO_32;
590
case EXPAND_8_TO_32: {
591
#if arch_is_big_endian
592
# define word_shift (shift)
594
int word_shift = 24 - shift;
596
for (y = 0; y < height;
597
++y, source_row += source->raster, dest_row += dest->raster
600
const byte *source = source_row;
601
bits32 *dest = (bits32 *)dest_row;
603
for (x = width; x > 0; --x)
604
*dest++ = (bits32)(*source++) << word_shift;
612
for (y = 0; y < height;
613
++y, source_row += source->raster, dest_row += dest->raster
616
sample_load_declare_setup(sptr, sbit, source_row, source_bit,
618
sample_store_declare_setup(dptr, dbit, dbbyte, dest_row, dest_bit,
621
sample_store_preload(dbbyte, dptr, dbit, dest_depth);
622
for (x = width; x > 0; --x) {
624
gx_color_index pixel;
626
sample_load_next8(color, sptr, sbit, source_depth);
627
pixel = color << shift;
628
sample_store_next_any(pixel, dptr, dbit, dest_depth, dbbyte);
630
sample_store_flush(dptr, dbit, dest_depth, dbbyte);
638
/* ---------------- Byte-oriented operations ---------------- */
640
/* Fill a rectangle of bytes. */
642
bytes_fill_rectangle(byte * dest, uint raster,
643
byte value, int width_bytes, int height)
645
while (height-- > 0) {
646
memset(dest, value, width_bytes);
651
/* Copy a rectangle of bytes. */
653
bytes_copy_rectangle(byte * dest, uint dest_raster,
654
const byte * src, uint src_raster, int width_bytes, int height)
656
while (height-- > 0) {
657
memcpy(dest, src, width_bytes);
added
removed
src/gsbitops.c
