[gs-code-review] 688177 Eliminate the 64 bit pixel size limit
Dan Coby
dan.coby at artifex.com
Wed Aug 31 00:25:25 PDT 2005
Note: The diff file included with this email, only implements this
enhancement for the tiffsep device. This change also needs to be done
for the psdcmyk, spotcmyk, and display devices since these also implement
support for more than 4 colorants. Even though this is incomplete, I
thought that I would send this out to get comments and suggestions upon
the ideas and/or the implementation.
This is a enhancement for how to work around the size limit imposed by
using a 64 bit integer value to represent a pixel.
This scheme involves encoding given colorants into a 64 bit gx_color_index
value. This is done by determining which of the given colorants are used (i.e.
non zero) and then keeping a list of the combinations of non zero colorants.
The non zero colorant values and an 'index' value are packed into
a gx_color_index value. When it is necessary to expand a gx_color_index
value back to colorant values, the 'index' value is used to find the colorant
combination in the list.
The number of bits allocated to storing the 'index' and the number of bits
allocated to storing depends upon the number of components being used.
Number of non zero components Index bits Bits per component
0 to 5 24 8
6 16 8
7 8 8
8 8 7
9 8 6
10 8 5
11 8 5
12 8 4
13 8 4
14 8 4
More than 14 Not enclosable
The 'index' bits can be logically divided into groups of 8 bits. The
first (upper) group of 8 bits is used to select either one of 256
combinations of 7 or more components or to select a pointer to a sub
level. If a sub level pointer is specified, then the next group of 8
index bits is used to select either one of 256 combinations of 6 components
of a sub level pointer. A sub level pointer points to one of 256
combinations of 5 components. If we have fewer than 5 components being
used, we add extra components to bring the total up to 5 components.
This is done to prevent having a bunch of 1 or two component combinations.
The table of component combinations is kept as a list with 256 elements.
Each element can be either a bit map which indicates the combination of
components being used or a pointer to a sub list for the next lower
level of combinations.
Advantages of this scheme:
1. This implementation localizes changes to the devices which need
to support more than 4 colorants. Thus changes to the majority of the
graphics library and other devices are not needed. (This is a BIG
advantage.)
2. This implementation only requires 8 bytes per pixel. The most obvious
scheme would add a byte for each colorant in the pixel. So support for
64 colorants would require 8 times as much memory for image buffers.
3. The size of a pixel does not need to change as more spot colors
are found in processing a file. This simplifies changing the number
of device colorants as a file is processed. By keeping fixed pixel
size, images buffers, etc. do not need to change as more spot colors
are found. To get around this problem, the current tiffsep and psdcmyk
devices always set their number of colorants to their max of 8 colorants.
This adds overhead for colorant processing (transfer functions, etc.)
for unused colorants. This would get worse with if the number of
colorants is increased.
4. The expansion of a pixel value back to colorant values is quick.
This is desired since this is needed for each pixel when the page is
printed.
5. The general idea of encoding colorant values in a gx_color_index
can be done many different ways. This scheme does not lock out other
possible methods. For instance, Igor has mentioned some scheme. However
I do not know the details of his scheme. The patches that he has posted
to 688177 do not give enough detail for evaluation of his scheme.
Disadvantages of this implementation and a quick discussion of each:
1. In theory it is possible for there to be combinations of colorant
values that cannot be represented by the given encoding scheme.
One of the important details of this scheme is that it is only encoding
the colorants which are non zero in each pixel. There can be different
combinations of colorants in different pixel locations. Since this scheme
can encode up to 14 non zero colorants in each pixel location, an image
with more than this would have a huge amount of ink on the page. Thus
this limit is probably only a theoretical problem.
2. For more than 7 colorants, this scheme uses fewer than 8 bits per
colorant. This can result in a loss of precision in the output.
So far, in our limited testing, the largest number of colorants per pixel
has been 6. Thus these files would have no loss of precision. The
reduced precision for 8 to 14 colorants was implemented primarily as a
fall back scheme for handling some unusual (and probably very unlikely)
cases.
3. It is possible for there to be millions of possible different combinations
of colorants being used in different pixels. Thus the table size can
grow to be huge. As a result, the search time in search_encode_color_list
could grow huge and the storage for saving these combinations would also
be extremely large. Note: A simple linear search is used which is quick
for a small number of entries but could get very slow with a large number of
entries.
This is possible. There are a couple of things which are done in the
implementation to try to minimize the explosion of combinations of colorants.
The list of colorant combinations is initialized with an initial entry
covering the first 7 colorants. Thus for files that use 7 or fewer colorants,
a single table entry is all that is required. For files with more than 7
colorants, more table entries are required. For these files and for pixels
with combinations with less than 5 colorants in a pixel, extra process colorants
added so that all table entries have at least 5 colorants. This is done to
prevent having a bunch of 2 or three colorant combinations.
So far, with our limited testing, in a file with 7 spot colorants, only 47
entries were used. The memory usage for this file was three list records.
One record each for the 7, 6, and 5 colorant levels. Each record is about
3 Kbytes. (The record size depends upon the desired maximum number of
possible colorants.)
4. There are only 256 possible combinations of 7 or more colorant combinations.
This is my best guess about the weakest link in this implementation. However
we do not have a real file that even needs more than the one 7 colorant entry
that is placed in the list at initialization. With 6 colorants, we can have as
many as 65280 entries.
5. This implementation does not do anything about 'object type tagging'.
This leaves something for the future.
6. This implementation does not allow much room for having more than 8 bits
for each colorant value.
Obviously trying to pack things into 64 bits is a little tight if one wants
more bits per components.
7. The implementation requires a 'non separable' pixel encoding. As a result,
the overprinting logic is not using its faster 'separable' handling logic.
Instead, overprinting is using get_bits and decode_color to get pixel colorant
values for merging with new overprint data. This is slower.
I have only run timing on one file. At 800 dpi, I get
New:
real 1m 1.20s
user 0m57.39s
sys 0m 2.15s
Old:
real 1m 0.82s
user 0m35.85s
sys 0m 2.51s
Thus there is a significant increase is user time. (But there is little change
in real time.) It is possible to add custom overprint logic for handling this
type of encoding. However I am not sure about the performance improvement.
8. The current implementation does not support switching between 1 bit halftoned
and 8 bit contone colorants.
Logically the task is not difficult.
9. This scheme requires 64 bit gx_color_index values.
Bug 687523 Add determining the length of gx_color_index to genarch.c would
allow putting in conditional compilation to the old implementation for 32 bit
gx_color_indexes. I am not very familiar with building on different linux
systems. Otherwise I would have fix this bug a long time ago. I doubt that
trying to implement the encoded pixel scheme used for 64 bits would likely
be made to work with only 32 bits.
A few final notes on supporting more than 64 colorants:
The current overprint implementation uses gx_color_index values to keep track
of which colorants are being imaged. This would need to be changed if support
for more than 64 colorants is desired.
The current halftone implementation requires a 'separable' pixel encoding for
more than 4 colorants. I have no idea about what would be required to implement
something logically similar to this scheme when halftoning. The current
scheme is limited to the number of bits in a gx_color_index (i.e. 64).
Dan
-------------- next part --------------
? src/.gdevdevn.c.swp
Index: src/gdevdevn.c
===================================================================
RCS file: /cvs/ghostscript/gs/src/gdevdevn.c,v
retrieving revision 1.26
diff -u -r1.26 gdevdevn.c
--- src/gdevdevn.c 9 Aug 2005 22:38:23 -0000 1.26
+++ src/gdevdevn.c 31 Aug 2005 04:26:26 -0000
@@ -443,17 +443,7 @@
case 0:
if (max_sep < 1 || max_sep > GX_DEVICE_COLOR_MAX_COMPONENTS)
return_error(gs_error_rangecheck);
- {
- int depth =
- bpc_to_depth(max_sep, pdevn_params->bitspercomponent);
-
- if (depth > 8 * size_of(gx_color_index))
- return_error(gs_error_rangecheck);
- pdevn_params->max_separations =
- pdev->color_info.max_components =
- pdev->color_info.num_components = max_sep;
- pdev->color_info.depth = depth;
- }
+ pdevn_params->max_separations = max_sep;
}
/*
* The DeviceN device can have zero components if nothing has been
@@ -540,6 +530,589 @@
return code;
}
+/*
+ * The following routines are for compressing colorant values into a 64 bit
+ * gx_color_index value. This is needed since Ghostscript uses an integer type
+ * (usually 64 bit long long) as the representation for a pixel. This is a
+ * problem for handling output device which support spot colors. Ideally these
+ * devices should be able to handle any number of colorants. This would require
+ * an arbitrarily large number of bits to represent a pixel.
+ *
+ * This scheme keeps track of which colorants are used when a set of color
+ * values are encoded into a pixel color value (a gx_color_index value). We create
+ * a list of which combinations of colorants are used in a table. The non zero
+ * colorant values are packed as 8 bit values in the gx_color_index. An 'index'
+ * is placed at the top of the gx_color_index value which allows us to search
+ * our table to get our list of which colorants are being used in the pixel.
+ */
+
+/* GC procedures */
+private
+ENUM_PTRS_WITH(encode_color_list_enum_ptrs, encode_color_list_t *plist)
+{
+ if (index < plist->num_sub_level_ptrs)
+ ENUM_RETURN(plist->u.sub_level_ptrs[index]);
+ return 0;
+}
+ENUM_PTRS_END
+
+private RELOC_PTRS_WITH(encode_color_list_reloc_ptrs, encode_color_list_t *plist)
+{
+ int i;
+
+ for (i = 0; i < plist->num_sub_level_ptrs; i++) {
+ RELOC_PTR(encode_color_list_t, u.sub_level_ptrs[i]);
+ }
+}
+RELOC_PTRS_END
+
+gs_private_st_composite(st_encode_color_list, encode_color_list_t,
+ "encode color list", encode_color_list_enum_ptrs,
+ encode_color_list_reloc_ptrs);
+/*
+ * A routine for debugging the encoded color component list. This routine
+ * dumps the contents of the list.
+ */
+void
+print_encode_color_list(encode_color_list_t * pcomp_list, int num_comp)
+{
+ int i, j, comp_num, comp;
+ comp_bit_map_list_t * pcomp_bit_map;
+
+ /* Indent our print out for sub levels */
+ for (i = TOP_ENCODED_LEVEL - pcomp_list->level_num_comp; i > 0; i--)
+ dlprintf(" ");
+ dlprintf1("List level = %d\n", pcomp_list->level_num_comp);
+ /*
+ * Print the component bit maps for this level.
+ */
+ for (i = NUM_ENCODE_LIST_ITEMS - 1; i >= pcomp_list->first_bit_map; i--) {
+ pcomp_bit_map = &(pcomp_list->u.comp_data[i]);
+ /* Indent our print out for sub levels */
+ for (j = TOP_ENCODED_LEVEL - pcomp_list->level_num_comp; j > 0; j--)
+ dlprintf(" ");
+ dlprintf2("%3d %4d ", i, pcomp_bit_map->num_comp);
+ for (comp_num = num_comp - 1; comp_num >= 0; comp_num--) {
+ comp = component_present(pcomp_bit_map, comp_num);
+ dlprintf1("%d", comp);
+ if ((comp_num & 7) == 0) /* Separate into groups of 8 bits */
+ dlprintf(" ");
+ }
+ dlprintf("\n");
+ }
+
+ /*
+ * Print the sub levels.
+ */
+ for (i = 0; i < pcomp_list->num_sub_level_ptrs; i++)
+ print_encode_color_list(pcomp_list->u.sub_level_ptrs[i], num_comp);
+
+ return;
+}
+
+/*
+ * Allocate an list level element for our encode color list.
+ */
+private encode_color_list_t *
+alloc_encode_color_list_elem(gs_memory_t * mem, int num_comps)
+{
+ encode_color_list_t * plist =
+ gs_alloc_struct(mem, encode_color_list_t, &st_encode_color_list,
+ "alloc_encode_color_list");
+ if (plist != NULL) {
+ /* Initialize the data in the element. */
+ memset(plist, 0, size_of(*plist));
+ plist->level_num_comp = num_comps;
+ plist->first_bit_map = NUM_ENCODE_LIST_ITEMS;
+ }
+ return plist;
+}
+
+/*
+ * Add a new bit mapped component list to our list of encoded color components.
+ */
+private bool
+add_encode_color_list(gs_memory_t * mem, comp_bit_map_list_t * pnew_comp_bit_map,
+ encode_color_list_t * pcomp_list, gx_color_index * plist_index)
+{
+ int i, entry_num;
+ int comp_count = pnew_comp_bit_map->num_comp;
+ bool status;
+
+ /*
+ * Check if this is the level for the specified number of entries. If so
+ * then add the bit map to this level (if we have room).
+ */
+ if (comp_count >= pcomp_list->level_num_comp) {
+ entry_num = pcomp_list->first_bit_map - 1;
+
+ if (entry_num > pcomp_list->num_sub_level_ptrs) {
+ memcpy(&(pcomp_list->u.comp_data[entry_num]), pnew_comp_bit_map,
+ size_of(comp_bit_map_list_t));
+ pcomp_list->first_bit_map = entry_num;
+ *plist_index =
+ ((gx_color_index) entry_num) << (NUM_GX_COLOR_INDEX_BITS - 8);
+ return true;
+ }
+ return false;
+ }
+ /*
+ * Try to insert the bit map into the sub levels.
+ */
+ for (i = 0; i < pcomp_list->num_sub_level_ptrs; i++) {
+ status = add_encode_color_list(mem, pnew_comp_bit_map,
+ pcomp_list->u.sub_level_ptrs[i], plist_index);
+ if (status) {
+ *plist_index = (((gx_color_index) i) << (NUM_GX_COLOR_INDEX_BITS - 8))
+ + (*plist_index >> 8);
+ return true;
+ }
+ }
+ /*
+ * If we did not add this bit map into a sub level then create a new sub
+ * level and insert it there.
+ */
+ entry_num = pcomp_list->num_sub_level_ptrs;
+ if (entry_num < pcomp_list->first_bit_map) {
+ pcomp_list->u.sub_level_ptrs[entry_num] =
+ alloc_encode_color_list_elem(mem, pcomp_list->level_num_comp - 1);
+ if (pcomp_list->u.sub_level_ptrs[entry_num] != NULL) {
+ pcomp_list->num_sub_level_ptrs++;
+ status = add_encode_color_list(mem, pnew_comp_bit_map,
+ pcomp_list->u.sub_level_ptrs[entry_num], plist_index);
+ if (status) {
+ *plist_index = (((gx_color_index) i) << (NUM_GX_COLOR_INDEX_BITS - 8))
+ + (*plist_index >> 8);
+ return true;
+ }
+ }
+ }
+ /*
+ * If we get to here then there was no space available in this list element.
+ */
+ return false;
+}
+
+/*
+ * Initialize our encode color list.
+ */
+private encode_color_list_t *
+init_encode_color_list(gs_memory_t *mem)
+{
+ /*
+ * Create our first list element.
+ */
+ encode_color_list_t * plist =
+ alloc_encode_color_list_elem(mem, TOP_ENCODED_LEVEL);
+
+ /*
+ * Add a first component bit map to the list. This bit map covers the first
+ * TOP_ENCODED_LEVEL colorants. Typically this covers CMYK plus the
+ * first three spot colors. This bit map should handle many situations.
+ */
+ if (plist != NULL) {
+ int comp_num;
+ comp_bit_map_list_t first_comp_bit_map = { 0 };
+ gx_color_index temp;
+
+ for (comp_num = 0; comp_num < TOP_ENCODED_LEVEL; comp_num++)
+ set_component_present(first_comp_bit_map, comp_num);
+ first_comp_bit_map.num_comp = TOP_ENCODED_LEVEL;
+ add_encode_color_list(mem, &first_comp_bit_map, plist, &temp);
+ }
+ return plist;
+}
+
+/*
+ * For most combinations of components we use 8 bits for saving the component
+ * value. However if we get above 7 components (in a pixel, not total) we use
+ * fewer bits. The constraint is that the size of the index value plus the
+ * the number of components being used times size of the component value saved
+ * must fit into a gx_color_index value.
+ */
+static int num_comp_bits[MAX_ENCODED_COMPONENTS + 1] = {
+ 8, /* 0 components - not used */
+ 8, /* 1 components */
+ 8, /* 2 components */
+ 8, /* 3 components */
+ 8, /* 4 components */
+ 8, /* 5 components */
+ 8, /* 6 components */
+ 8, /* 7 components */
+ 7, /* 8 components */
+ 6, /* 9 components */
+ 5, /* 10 components */
+ 5, /* 11 components */
+ 4, /* 12 components */
+ 4, /* 13 components */
+ 4 /* 14 components */
+};
+
+/*
+ * Values used to decompressed the components in our encoded values back into
+ * a gx_color value. The color value will be (comp_bits * entry) >> 8
+ * The number of bits in comp_bits are defined in the num_comp_bits table.
+ * These values are chosen to expand these bit combinations back to 16 bit values.
+ */
+static int comp_bit_factor[MAX_ENCODED_COMPONENTS + 1] = {
+ (1 << 16) + (1 << 8), /* 0 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 1 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 2 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 3 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 4 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 5 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 6 components (8 bits) */
+ (1 << 16) + (1 << 8), /* 7 components (8 bits) */
+ (1 << 17) + (1 << 10) + (1 << 3), /* 8 components (7 bits) */
+ (1 << 18) + (1 << 12) + (1 << 6), /* 9 components (6 bits) */
+ (1 << 19) + (1 << 14) + (1 << 9) + (1 << 4), /* 10 components (5 bits) */
+ (1 << 19) + (1 << 14) + (1 << 9) + (1 << 4), /* 11 components (5 bits) */
+ (1 << 20) + (1 << 16) + (1 << 12) + (1 << 8),/* 12 components (4 bits) */
+ (1 << 20) + (1 << 16) + (1 << 12) + (1 << 8),/* 13 components (4 bits) */
+ (1 << 20) + (1 << 16) + (1 << 12) + (1 << 8) /* 14 components (4 bits) */
+};
+
+/*
+ * Find a given component bit map is the list of encoded component bit map.
+ *
+ * Note: This routine is called recursively to search sub levels of the
+ * list.
+ *
+ * The parameters are:
+ * num_comp - The number of components for the device.
+ * pcomp_list - The current list of encoded components.
+ * comp_num - The number of components to be encoded.
+ * pnew_comp_bit_map - Pointer to the bit map found to be encoded.
+ * plist_index - Pointer to 'encode bits' (return value)
+ * pcomp_bit_map - Pointer to pointer to the actual bit map found
+ * (return value).
+ * returns true if the bit map is found.
+ */
+private bool
+search_encode_color_list(int num_comp, encode_color_list_t * pcomp_list,
+ int comp_num, comp_bit_map_list_t * pnew_comp_bit_map,
+ gx_color_index * plist_index, comp_bit_map_list_t * * pcomp_bit_map)
+{
+ int i;
+#if DEVN_ENCODE_COLOR_USING_BIT_MAP_ARRAY
+ int j, num_bit_map_elem;
+#endif
+ bool found;
+
+ /*
+ * Search the component bit maps for this level of the map.
+ */
+#if DEVN_ENCODE_COLOR_USING_BIT_MAP_ARRAY
+ num_bit_map_elem = (num_comp + BITS_PER_COMP_BIT_MAP_ELEM - 1) /
+ BITS_PER_COMP_BIT_MAP_ELEM;
+#endif
+ for (i = NUM_ENCODE_LIST_ITEMS - 1; i >= pcomp_list->first_bit_map; i--) {
+ *pcomp_bit_map = &(pcomp_list->u.comp_data[i]);
+ /*
+ * It is a match if the new component bit map is a subset of the one
+ * in the list.
+ */
+#if DEVN_ENCODE_COLOR_USING_BIT_MAP_ARRAY
+ for (j = 0; j < num_bit_map_elem; j++) {
+ if ((pnew_comp_bit_map->components[j] &
+ (*pcomp_bit_map)->components[j]) !=
+ pnew_comp_bit_map->components[j])
+ break; /* No match if a component is missing. */
+ }
+ if (j == num_bit_map_elem) {
+#else
+ if ((pnew_comp_bit_map->components & (*pcomp_bit_map)->components) ==
+ pnew_comp_bit_map->components) {
+#endif
+ /*
+ * To prevent possible loss of accuracy, ignore matches in which the
+ * packing will use fewer bits in the encoded component values than
+ * is possible for the given number of components.
+ */
+ if (num_comp_bits[pnew_comp_bit_map->num_comp] >
+ num_comp_bits[(*pcomp_bit_map)->num_comp])
+ break;
+ /*
+ * We have a match. Put our object number into the top eight
+ * bits of the encoded gx_color_index and exit.
+ */
+ *plist_index = ((gx_color_index) i) << (NUM_GX_COLOR_INDEX_BITS - 8);
+ return true;
+ }
+ }
+
+ /*
+ * Search the lower levels (i.e. with fewer components to see if we
+ * can find a match.
+ */
+ if (pcomp_list->level_num_comp <= comp_num)
+ return false; /* Exit if not enough components in the sub levels */
+ for (i = 0; i < pcomp_list->num_sub_level_ptrs; i++) {
+ found = search_encode_color_list(num_comp, pcomp_list->u.sub_level_ptrs[i],
+ comp_num, pnew_comp_bit_map, plist_index, pcomp_bit_map);
+ if (found) {
+ /*
+ * We have a match. Combine the encode index for the sub level
+ * with our index for this level.
+ */
+ *plist_index = (((gx_color_index) i) << (NUM_GX_COLOR_INDEX_BITS - 8))
+ + (*plist_index >> 8);
+ return true;
+ }
+ }
+ return false;
+}
+
+/*
+ * Encode a list of colorant values into a gx_color_index_value.
+ *
+ * This routine is designed to pack more than eight 8 bit colorant values into
+ * a 64 bit gx_color_index value. It does this piece of magic by keeping a list
+ * of which colorant combinations are actualy used (i.e. which colorants are non
+ * zero). The non zero colorant values and and an 'index' value are packed into
+ * the output gx_color_index value.
+ *
+ * The number of bits allocated to storing the 'index' and the number of bits
+ * allocated to storing depends upon the number of components be used.
+ * Number of non zero components Index bits Bits per component
+ * 0 to 5 24 8
+ * 6 16 8
+ * 7 8 8
+ * 8 8 7
+ * 9 8 6
+ * 10 8 5
+ * 11 8 5
+ * 12 8 4
+ * 13 8 4
+ * 14 8 4
+ * More than 14 Not encodable
+ *
+ * The 'index' bits can be logically divided into groups of 8 bits. The
+ * first (upper) group of 8 bits is used to select either one of 256
+ * combinations of 7 or more components or to select a pointer to a sub
+ * level. If a sub level pointer is specified, then the next group of 8
+ * index bits is used to select either one of 256 combinations of 6 components
+ * of a sub level pointer. A sub level pointer points to one of 256
+ * combinations of 5 components. If we have fewer than 5 components being
+ * used, we add extra componnents to bring the total up to 5 components.
+ * This is done to prevent having a bunch of 1 or two component combinations.
+ *
+ * The table of component combinations is kept as a list with 256 elements.
+ * Each element can be either a bit map which indicates the combination of
+ * components being used or a pointer to a sub list for the next lower
+ * level of combiations.
+ */
+gx_color_index
+devn_encode_color(gx_device *pdev, const gx_color_value colors[],
+ gs_devn_params * pdevn_params)
+{
+ int num_comp = pdev->color_info.num_components;
+ int comp_num, comp_count = 0, bit_pos = 0;
+ int bit_shift, bit_count;
+ bool found, added;
+ comp_bit_map_list_t new_comp_bit_map = {0};
+ comp_bit_map_list_t * pbit_map;
+ gx_color_index color = 0, list_index;
+
+ /*
+ * Determine what components are being used (non zero). We bit pack
+ * this info. Note: We treat any colorant value which is less than
+ * 256 as zero. Color values are 16 bits and we only keep the top
+ * eight bits.
+ */
+ for (comp_num = 0; comp_num < num_comp; comp_num++) {
+ if (colors[comp_num] >= 256) {
+ set_component_present(new_comp_bit_map, comp_num);
+ comp_count++;
+ }
+ }
+ new_comp_bit_map.num_comp = comp_count;
+ /* Our encoding scheme cannot handle too many components. */
+ if (comp_count > MAX_ENCODED_COMPONENTS)
+ return NON_ENCODEABLE_COLOR;
+
+ /*
+ * We keep a list of which component combinations we have used. Make
+ * sure that this list has been initialized.
+ */
+ if (pdevn_params->encode_color_list == NULL) {
+ pdevn_params->encode_color_list = init_encode_color_list(pdev->memory);
+ if (pdevn_params->encode_color_list == NULL)
+ return NON_ENCODEABLE_COLOR; /* Unable to initialize list */
+ }
+
+ /*
+ * Check our list of component combinations to see if we already have a
+ * combination that is useable. I.e. a combination that includes all of our
+ * non zero components.
+ */
+ found =
+ search_encode_color_list(num_comp, pdevn_params->encode_color_list,
+ comp_count, &new_comp_bit_map, &list_index, &pbit_map);
+
+ /*
+ * If our new component list was not found then add it to our encode color
+ * list.
+ */
+ if (!found) {
+ /*
+ * Our simple linear search for entries gets very inefficient if we
+ * have many entries. Thus we do not want to have a bunch of entries
+ * with only a few components. For small numbers of components, we
+ * add more components to try to create an entry that can be used for
+ * more situations. We add extra process color components since these
+ * are the ones most likely to be mixed with spot colors.
+ */
+ for (comp_num = 0; comp_count < MIN_ENCODED_COMPONENTS; comp_num++) {
+ if ((component_present(&new_comp_bit_map, comp_num)) == 0) {
+ set_component_present(new_comp_bit_map, comp_num);
+ comp_count++;
+ }
+ }
+ new_comp_bit_map.num_comp = comp_count;
+ added = add_encode_color_list(pdev->memory, &new_comp_bit_map,
+ pdevn_params->encode_color_list, &list_index);
+ if (!added)
+ return NON_ENCODEABLE_COLOR;
+ pbit_map = &new_comp_bit_map;
+ }
+
+ /*
+ * Form the encoded color gx_color_index value. This is a combination
+ * of the bits that encode which components are used (non zero) and the
+ * component values.
+ */
+ bit_count = num_comp_bits[pbit_map->num_comp];
+ bit_shift = sizeof(gx_color_value) * 8 - bit_count;
+ for (comp_num = 0; comp_num < num_comp; comp_num++) {
+ if (component_present(pbit_map, comp_num)) {
+ color |=
+ ((gx_color_index)(colors[comp_num] >> bit_shift)) << bit_pos;
+ bit_pos += bit_count;
+ }
+ }
+ color |= list_index;
+ /*
+ * Make sure that our color index does not match one of the reserved
+ * values.
+ */
+ // dlprintf2("color = %08x %08x\n", (int) (color >> 32), (int)color);
+ if (color == NON_ENCODEABLE_COLOR)
+ color -= 1;
+ else if (color == gx_no_color_index)
+ color -= 2;
+ return color;
+}
+
+/*
+ * Find the bit map for given bit map index.
+ */
+private comp_bit_map_list_t *
+find_bit_map(gx_color_index index, encode_color_list_t * pcomp_list)
+{
+ int loc = (int)(index >> (NUM_GX_COLOR_INDEX_BITS - 8));
+
+ /*
+ * Search for the level which contains the bit map.
+ */
+ while (loc < pcomp_list->num_sub_level_ptrs) {
+ pcomp_list = pcomp_list->u.sub_level_ptrs[loc];
+ index <<= 8;
+ loc = (int)(index >> (NUM_GX_COLOR_INDEX_BITS - 8));
+ }
+ return &(pcomp_list->u.comp_data[loc]);
+}
+
+/*
+ * Decode a gx_color_index value back to a list of colorant values. This
+ * routine assumes that the gx_color_index value is 'encoded' as described
+ * for devn_encode_color.
+ */
+int
+devn_decode_color(gx_device * dev, gx_color_index color, gx_color_value * out,
+ gs_devn_params * pdevn_params)
+{
+ int comp_num = 0;
+ int factor, bit_count, bit_mask;
+ int ncomp = dev->color_info.num_components;
+ comp_bit_map_list_t * pbitmap;
+
+ /*
+ * Set all components to max if we get a non encodeable color. We set the
+ * values to a max since this will represent another non encodable color.
+ * Thus if we have a non decodable color, it will continue to propogate.
+ */
+ if (color == NON_ENCODEABLE_COLOR) {
+ for (; comp_num < ncomp; comp_num++)
+ out[comp_num] = gx_max_color_value;
+ return 0;
+ }
+ pbitmap = find_bit_map(color, pdevn_params->encode_color_list);
+ bit_count = num_comp_bits[pbitmap->num_comp];
+ bit_mask = (1 << bit_count) - 1;
+ factor = comp_bit_factor[pbitmap->num_comp];
+ for (; comp_num < ncomp; comp_num++) {
+ if (component_present(pbitmap, comp_num)) {
+ out[comp_num] = (factor * ((int)color & bit_mask)) >> 8;
+ color >>= bit_count;
+ }
+ else
+ out[comp_num] = 0;
+ }
+ return 0;
+}
+
+
+/*
+ * Unpack a row of 'encoded color' values. These values are encoded as
+ * described for the devn_encode_color routine.
+ *
+ * The routine takes a raster line of data and expands each pixel into a buffer
+ * of 8 bit values for each colorant.
+ */
+int
+devn_unpack_row(gx_device * dev, int num_comp, gs_devn_params * pdevn_params,
+ int width, byte * in, byte * out)
+{
+ int i, comp_num, pixel_num, non_encodable_count = 0;
+ int factor, bit_count, bit_mask;
+ comp_bit_map_list_t * pbitmap;
+ gx_color_index color;
+
+ for (pixel_num = 0; pixel_num < width; pixel_num++) {
+ /*
+ * Get the encoded color value.
+ */
+ color = ((gx_color_index)(*in++)) << (NUM_GX_COLOR_INDEX_BITS - 8);
+ for (i = NUM_GX_COLOR_INDEX_BITS - 16; i >= 0; i -= 8)
+ color |= ((gx_color_index)(*in++)) << i;
+ /*
+ * Set all components to zero if we get a non encodeable color.
+ */
+ if (color == NON_ENCODEABLE_COLOR) {
+ for (comp_num = 0; comp_num < num_comp; comp_num++)
+ *out++ = 0;
+ non_encodable_count++;
+ }
+ else {
+ pbitmap = find_bit_map(color, pdevn_params->encode_color_list);
+ bit_count = num_comp_bits[pbitmap->num_comp];
+ bit_mask = (1 << bit_count) - 1;
+ factor = comp_bit_factor[pbitmap->num_comp];
+ for (comp_num = 0; comp_num < num_comp; comp_num++) {
+ if (component_present(pbitmap, comp_num)) {
+ *out++ = (factor * ((int)color & bit_mask)) >> 16;
+ color >>= bit_count;
+ }
+ else
+ *out++ = 0;
+ }
+ }
+ }
+ return non_encodable_count;
+}
+
+
/* ***************** The spotcmyk and devicen devices ***************** */
/* Define the device parameters. */
Index: src/gdevdevn.h
===================================================================
RCS file: /cvs/ghostscript/gs/src/gdevdevn.h,v
retrieving revision 1.11
diff -u -r1.11 gdevdevn.h
--- src/gdevdevn.h 8 Jul 2005 22:04:31 -0000 1.11
+++ src/gdevdevn.h 31 Aug 2005 04:26:26 -0000
@@ -60,6 +60,7 @@
* Type for holding a separation order map
*/
typedef int gs_separation_map[GX_DEVICE_MAX_SEPARATIONS];
+typedef struct encode_color_list_s encode_color_list_t;
typedef struct gs_devn_params_s {
/*
@@ -92,6 +93,10 @@
* components.
*/
gs_separation_map separation_order_map;
+ /*
+ * Pointer to our list of which colorant combinations are being used.
+ */
+ encode_color_list_t * encode_color_list;
} gs_devn_params_t;
typedef gs_devn_params_t gs_devn_params;
@@ -246,4 +251,183 @@
*/
int bpc_to_depth(int ncomp, int bpc);
+
+/*
+ * We are encoding color values into a gx_color_index value. This is being
+ * done to allow more than eight 8 bit colorant values to be stored inside
+ * of a 64 bit gx_color_index value.
+ *
+ * This is done by only keeping track of non zero colorant values. We
+ * keep a record of different colorant which combinations of colorants are
+ * used inside of the device and encode an index for the colorant combinations
+ * into the gx_color_index value.
+ */
+/*
+ * We are using bytes to pack both which components are non zero and the values
+ * of the components. Thus do not change this value without recoding the
+ * methods used for encoding our components.
+ */
+#define NUM_ENCODE_LIST_ITEMS 256
+
+/*
+ * Since we are byte packing things in a gx_color_index. We need the number
+ * of bytes in a gx_color_index.
+ */
+#define NUM_GX_COLOR_INDEX_BYTES size_of(gx_color_index)
+#define NUM_GX_COLOR_INDEX_BITS (8 * NUM_GX_COLOR_INDEX_BYTES)
+
+/*
+ * Define the highest level in our encoded color component list.
+ * Since we need at least one byte to store our encoded list of components
+ * and we are packing component values in bytes, the top level of our encoded
+ * color components that is the size of gx_clor_index - 1.
+ */
+#define TOP_ENCODED_LEVEL (NUM_GX_COLOR_INDEX_BYTES - 1)
+
+/*
+ * The maximum number of components that we can encode.
+ */
+#define MAX_ENCODED_COMPONENTS 14
+
+/*
+ * To prevent having a bunch of one or two component elements, we set a
+ * cutoff for the minimum number of components. If we have less than the
+ * cutoff then we add in our process colors on the assumption that it is
+ * likely that sometime we will want a combination of the process and spot
+ * colors.
+ */
+#define MIN_ENCODED_COMPONENTS 5
+
+/*
+ * Define a value to represent a color value that we cannot encode. This can
+ * occur if either we exceed MAX_ENCODED_COMPONENTS or all of the possible
+ * levels of the encoded component list are full.
+ */
+#define NON_ENCODEABLE_COLOR (gx_no_color_index - 1)
+
+/*
+ * We keep a bit map of the components.
+ *
+ * Ideally this comparison should be:
+ * #if GX_DEVICE_COLOR_MAX_COMPONENTS <= (sizeof(gx_color_index) * 8)
+ * but C compilers do not allow this contruct.
+ */
+#if GX_DEVICE_COLOR_MAX_COMPONENTS <= 64
+typedef gx_color_index comp_bit_map_t;
+#define set_component_present(bit_map, comp_num)\
+ bit_map.components |= (((gx_color_index)1) << comp_num)
+#define component_present(pbit_map, comp_num)\
+ ((int)(((pbit_map)->components >> comp_num)) & 1)
+/*
+ * The compare bit map soutine (for the array case) is too complex for a simple
+ * macro. So it is comditionally compiled using this switch.
+ */
+#define DEVN_ENCODE_COLOR_USING_BIT_MAP_ARRAY 0
+
+#else
+/*
+ * If we are trying to handle more components than will fit into a gx_color_index,
+ * then we bit pack them into uints. So we need to define some values for
+ * defining the number of elements that we need, etc.
+ */
+#define comp_bit_map_elem_t uint
+#define BITS_PER_COMP_BIT_MAP_ELEM (size_of(comp_bit_map_elem_t) * 8)
+#define COMP_BIT_MAP_ELEM_MASK (BITS_PER_COMP_BIT_MAP_ELEM - 1)
+
+#define COMP_BIT_MAP_SIZE \
+ ((GX_DEVICE_COLOR_MAX_COMPONENTS + COMP_BIT_MAP_ELEM_MASK) / \
+ BITS_PER_COMP_BIT_MAP_ELEM)
+
+/* Bit map list of components in the gx_color_index value */
+typedef comp_bit_map_elem_t comp_bit_map_t[COMP_BIT_MAP_SIZE];
+#define set_component_present(bit_map, comp_num)\
+ bit_map.components[comp_num / BITS_PER_COMP_BIT_MAP_ELEM] |=\
+ (1 << (comp_num & COMP_BIT_MAP_ELEM_MASK))
+#define component_present(pbit_map, comp_num)\
+ ((pbit_map)->components[comp_num / BITS_PER_COMP_BIT_MAP_ELEM] >>\
+ ((comp_num & COMP_BIT_MAP_ELEM_MASK)) & 1)
+/*
+ * The compare bit map soutine is too complex for s simple macro.
+ * So it is comditionally compiled using this switch.
+ */
+#define DEVN_ENCODE_COLOR_USING_BIT_MAP_ARRAY 1
+#endif
+
+/*
+ * The component bit map list struct.
+ */
+typedef struct comp_bit_map_list_s {
+ int num_comp;
+ comp_bit_map_t components;
+} comp_bit_map_list_t;
+
+/*
+ * Encoded component list level element definition.
+ *
+ * Each list level contains a list of objects. An object can be either a
+ * component bit map or a pointer to a sub list. We start our sub level
+ * pointer at zero and work up. Component bit maps are started at the top and
+ * go down. When they meet in the middle, then this list level element is full.
+ * Note: We start with the bit maps in the upper positions to ensure that
+ * gx_no_color_index and NON_ENCODEABLE_COLOR values correspond to 7 component
+ * cases. This is less likely to occur and less likely to cause a problem
+ * when we tweak the outputs to keep actual gx_color_index values from
+ * being one of these two special cases.
+ */
+typedef struct encode_color_list_s {
+ /*
+ * The number of components for this level of the encoded color list.
+ * Note: Each sub level encodes one fewer components.
+ */
+ int level_num_comp;
+ /* The number of sub level list pointers */
+ int num_sub_level_ptrs;
+ /* The current lower limit for the component bit maps */
+ int first_bit_map;
+ /*
+ * Use a union since an object is either a sub level pointer or a component
+ * bit map but not both.
+ */
+ union {
+ struct encode_color_list_s * sub_level_ptrs[NUM_ENCODE_LIST_ITEMS];
+ comp_bit_map_list_t comp_data[NUM_ENCODE_LIST_ITEMS];
+ } u;
+} encode_color_list_t;
+
+/*
+ * Encode a list of colorant values into a gx_color_index_value.
+ *
+ * This routine is designed to pack more than eight 8 bit colorant values into
+ * a 64 bit gx_color_index value. It does this piece of magic by keeping a list
+ * of which colorant combinations are actualy used (i.e. which colorants are non
+ * zero). The non zero colorant values and and an 'index' value are packed into
+ * the output gx_color_index value.
+ */
+gx_color_index devn_encode_color(gx_device *pdev, const gx_color_value colors[],
+ gs_devn_params * pdevn_params);
+
+/*
+ * Decode a gx_color_index value back to a list of colorant values. This
+ * routine assumes that the gx_color_index value is 'encoded' as described
+ * for devn_encode_color.
+ */
+int devn_decode_color(gx_device * dev, gx_color_index color, gx_color_value * out,
+ gs_devn_params * pdevn_params);
+
+/*
+ * A routine for debugging the encoded color component list. This routine
+ * dumps the contents of the list.
+ */
+void print_encode_color_list(encode_color_list_t * pcomp_list, int num_comp);
+
+/*
+ * Unpack a row of 'encoded color' values. These values are encoded as
+ * described for the devn_encode_color routine.
+ *
+ * The routine takes a raster line of data and expands each pixel into a buffer
+ * of 8 bit values for each colorant.
+ */
+int devn_unpack_row(gx_device * dev, int num_comp, gs_devn_params * pdevn_params,
+ int width, byte * in, byte * out);
+
#endif /* ifndef gdevdevn_INCLUDED */
Index: src/gdevmem.h
===================================================================
RCS file: /cvs/ghostscript/gs/src/gdevmem.h,v
retrieving revision 1.7
diff -u -r1.7 gdevmem.h
--- src/gdevmem.h 22 Aug 2002 07:12:28 -0000 1.7
+++ src/gdevmem.h 31 Aug 2005 04:26:26 -0000
@@ -172,7 +172,16 @@
gx_default_create_compositor,\
gx_default_get_hardware_params,\
gx_default_text_begin,\
- gx_default_finish_copydevice\
+ gx_default_finish_copydevice,\
+ NULL, /* begin_transparency_group */\
+ NULL, /* end_transparency_group */\
+ NULL, /* begin_transparency_mask */\
+ NULL, /* end_transparency_mask */\
+ NULL, /* discard_transparency_layer */\
+ NULL, /* get_color_mapping_procs */\
+ NULL, /* get_color_comp_index */\
+ map_rgb_color, /* encode_color */\
+ map_color_rgb, /* decode_color */\
},\
0, /* target */\
mem_device_init_private /* see gxdevmem.h */\
Index: src/gdevtsep.c
===================================================================
RCS file: /cvs/ghostscript/gs/src/gdevtsep.c,v
retrieving revision 1.8
diff -u -r1.8 gdevtsep.c
--- src/gdevtsep.c 9 Aug 2005 22:38:23 -0000 1.8
+++ src/gdevtsep.c 31 Aug 2005 04:26:27 -0000
@@ -260,13 +260,17 @@
private
ENUM_PTRS_WITH(tiffsep_device_enum_ptrs, tiffsep_device *pdev)
{
+ if (index == 0)
+ ENUM_RETURN(pdev->devn_params.encode_color_list);
+ index--;
if (index < pdev->devn_params.separations.num_separations)
ENUM_RETURN(pdev->devn_params.separations.names[index].data);
ENUM_PREFIX(st_device_printer,
pdev->devn_params.separations.num_separations);
+ return 0;
}
-
ENUM_PTRS_END
+
private RELOC_PTRS_WITH(tiffsep_device_reloc_ptrs, tiffsep_device *pdev)
{
RELOC_PREFIX(st_device_printer);
@@ -277,6 +281,7 @@
RELOC_PTR(tiffsep_device, devn_params.separations.names[i].data);
}
}
+ RELOC_PTR(tiffsep_device, devn_params.encode_color_list);
}
RELOC_PTRS_END
@@ -371,7 +376,7 @@
depth, 0, /* Depth, GrayIndex */\
mg, mc, /* MaxGray, MaxColor */\
mg + 1, mc + 1, /* DitherGray, DitherColor */\
- GX_CINFO_SEP_LIN, /* Linear & Separable */\
+ GX_CINFO_SEP_LIN_NONE, /* Not Linear & Separable */\
cn, /* Process color model name */\
0, 0, /* offsets */\
0, 0, 0, 0 /* margins */\
@@ -385,7 +390,9 @@
* Select the default number of components based upon the number of bits
* that we have in a gx_color_index
*/
-#define NC ((arch_sizeof_color_index <= 8) ? arch_sizeof_color_index : 8)
+#define NC ((arch_sizeof_color_index < 8) ? arch_sizeof_color_index \
+ : GX_DEVICE_COLOR_MAX_COMPONENTS)
+#define GCIB (arch_sizeof_color_index * 8)
/*
* TIFF device with CMYK process color model and spot color support.
@@ -394,12 +401,12 @@
const tiffsep_device gs_tiffsep_device =
{
- tiffsep_device_body(spot_cmyk_procs, "tiffsep", NC, GX_CINFO_POLARITY_SUBTRACTIVE, NC * 8, MAX_COLOR_VALUE, MAX_COLOR_VALUE, "DeviceCMYK"),
+ tiffsep_device_body(spot_cmyk_procs, "tiffsep", NC, GX_CINFO_POLARITY_SUBTRACTIVE, GCIB, MAX_COLOR_VALUE, MAX_COLOR_VALUE, "DeviceCMYK"),
/* devn_params specific parameters */
- { 8, /* Bits per color - must match ncomp, depth, etc. above */
+ { 8, /* Not used - Bits per color */
DeviceCMYKComponents, /* Names of color model colorants */
4, /* Number colorants for CMYK */
- NC, /* MaxSeparations: our current limit is 8 bytes */
+ NC, /* MaxSeparations */
{0}, /* SeparationNames */
{0}, /* SeparationOrder names */
{0, 1, 2, 3, 4, 5, 6, 7 } /* Initial component SeparationOrder */
@@ -454,23 +461,14 @@
{
return &tiffsep_cm_procs;
}
+
/*
* Encode a list of colorant values into a gx_color_index_value.
*/
private gx_color_index
tiffsep_encode_color(gx_device *dev, const gx_color_value colors[])
{
- int bpc = ((tiffsep_device *)dev)->devn_params.bitspercomponent;
- int drop = sizeof(gx_color_value) * 8 - bpc;
- gx_color_index color = 0;
- int i = 0;
- int ncomp = dev->color_info.num_components;
-
- for (; i < ncomp; i++) {
- color <<= bpc;
- color |= (colors[i] >> drop);
- }
- return (color == gx_no_color_index ? color ^ 1 : color);
+ return devn_encode_color(dev, colors, &(((tiffsep_device *)dev)->devn_params));
}
/*
@@ -479,17 +477,8 @@
private int
tiffsep_decode_color(gx_device * dev, gx_color_index color, gx_color_value * out)
{
- int bpc = ((tiffsep_device *)dev)->devn_params.bitspercomponent;
- int drop = sizeof(gx_color_value) * 8 - bpc;
- int mask = (1 << bpc) - 1;
- int i = 0;
- int ncomp = dev->color_info.num_components;
-
- for (; i < ncomp; i++) {
- out[ncomp - i - 1] = (gx_color_value) ((color & mask) << drop);
- color >>= bpc;
- }
- return 0;
+ return devn_decode_color(dev, color, out,
+ &(((tiffsep_device *)dev)->devn_params));
}
/*
@@ -695,8 +684,6 @@
{
int code = gdev_prn_open(pdev);
- set_linear_color_bits_mask_shift(pdev);
- pdev->color_info.separable_and_linear = GX_CINFO_SEP_LIN;
return code;
}
@@ -786,7 +773,7 @@
*/
private void
build_cmyk_raster_line(byte * src, byte * dest, int width,
- int num_comp, int pixel_size, cmyk_composite_map * cmyk_map)
+ int num_comp, cmyk_composite_map * cmyk_map)
{
int pixel, comp_num;
uint temp, cyan, magenta, yellow, black;
@@ -808,7 +795,6 @@
black += cmyk_map_entry->k * temp;
cmyk_map_entry++;
}
- src += pixel_size - num_comp;
cyan /= frac_1;
magenta /= frac_1;
yellow /= frac_1;
@@ -850,6 +836,9 @@
int save_depth = pdev->color_info.depth;
const char *fmt;
gs_parsed_file_name_t parsed;
+ int non_encodable_count = 0;
+
+ print_encode_color_list(tfdev->devn_params.encode_color_list, pdev->color_info.num_components);
build_comp_to_sep_map(tfdev, map_comp_to_sep);
@@ -926,13 +915,14 @@
int raster = gdev_prn_raster(pdev);
int width = tfdev->width;
int cmyk_raster = width * NUM_CMYK_COMPONENTS;
- int bytes_pp = tfdev->color_info.num_components;
int pixel, y;
byte * line = gs_alloc_bytes(pdev->memory, raster, "tiffsep_print_page");
+ byte * unpacked = gs_alloc_bytes(pdev->memory, width * num_comp,
+ "tiffsep_print_page");
byte * sep_line;
byte * row;
- if (line == NULL)
+ if (line == NULL || unpacked == NULL)
return_error(gs_error_VMerror);
sep_line =
gs_alloc_bytes(pdev->memory, cmyk_raster, "tiffsep_print_page");
@@ -946,18 +936,21 @@
code = gdev_prn_get_bits(pdev, y, line, &row);
if (code < 0)
break;
+ /* Unpack the encoded color info */
+ non_encodable_count += devn_unpack_row((gx_device *)pdev, num_comp,
+ &(tfdev->devn_params), width, row, unpacked);
/* Write separation data (tiffgray format) */
for (comp_num = 0; comp_num < num_comp; comp_num++ ) {
- byte * src = row + comp_num;
+ byte * src = unpacked + comp_num;
byte * dest = sep_line;
- for (pixel = 0; pixel < width; pixel++, dest++, src += bytes_pp)
+ for (pixel = 0; pixel < width; pixel++, dest++, src += num_comp)
*dest = MAX_COLOR_VALUE - *src; /* Gray is additive */
fwrite((char *)sep_line, width, 1, tfdev->sep_file[comp_num]);
}
/* Write CMYK equivalent data (tiff32nc format) */
- build_cmyk_raster_line(row, sep_line, width,
- num_comp, bytes_pp, cmyk_map);
+ build_cmyk_raster_line(unpacked, sep_line,
+ width, num_comp, cmyk_map);
fwrite((char *)sep_line, cmyk_raster, 1, file);
}
/* Update the strip data */
@@ -973,5 +966,9 @@
gs_free_object(pdev->memory, sep_line, "tiffsep_print_page");
}
+ if (non_encodable_count)
+ dlprintf1("WARNING: Non encodable pixels = %d\n", non_encodable_count);
+
return code;
}
+
More information about the gs-code-review
mailing list