diff options
author | Robin Watts <robin.watts@artifex.com> | 2015-03-13 17:09:29 +0000 |
---|---|---|
committer | Robin Watts <robin.watts@artifex.com> | 2015-03-24 19:50:01 +0000 |
commit | 33c49228d078cc963ac5e59e526c97d2fd50a01f (patch) | |
tree | 233e29c78e497ca3b4d90bb3ea03ab846b61fbc6 /source | |
parent | 5f161e45d5daacb696d02b8fad23d0c23f5bc8bc (diff) | |
download | mupdf-33c49228d078cc963ac5e59e526c97d2fd50a01f.tar.xz |
Path packing for memory efficiency.
Introduce the concept of 'packed' paths. These reduce the header
overhead for most common paths (ones with less than 256 commands
and 256 coords) to a single 32bit int once stored in the
display list.
The previous commit reduces the torture-test.pdf from 95 to 87Meg.
This commit futher reduces it to 70Meg.
Diffstat (limited to 'source')
-rw-r--r-- | source/fitz/list-device.c | 69 | ||||
-rw-r--r-- | source/fitz/path.c | 315 |
2 files changed, 282 insertions, 102 deletions
diff --git a/source/fitz/list-device.c b/source/fitz/list-device.c index 738499b1..038517b4 100644 --- a/source/fitz/list-device.c +++ b/source/fitz/list-device.c @@ -71,7 +71,7 @@ typedef enum fz_display_command_e * flags: Flags (node specific meanings) * * Nodes are packed in the order: - * header, rect, path, colorspace, color, alpha, ctm, stroke_state, private data. + * header, rect, colorspace, color, alpha, ctm, stroke_state, path, private data. */ struct fz_display_node_s { @@ -105,7 +105,9 @@ enum { CTM_UNCHANGED = 0, CTM_CHANGE_AD = 1, CTM_CHANGE_BC = 2, - CTM_CHANGE_EF = 4 + CTM_CHANGE_EF = 4, + + MAX_NODE_SIZE = (1<<9)-sizeof(fz_display_node) }; struct fz_display_list_s @@ -176,6 +178,7 @@ fz_append_display_node( fz_path *my_path = NULL; fz_stroke_state *my_stroke = NULL; fz_rect local_rect; + int path_size = 0; switch (cmd) { @@ -242,7 +245,7 @@ fz_append_display_node( } /* fallthrough */ default: - if (writer->top > 0 && writer->tiled == 0 && writer->top <= STACK_SIZE) + if (writer->top > 0 && writer->tiled == 0 && writer->top <= STACK_SIZE && rect) fz_union_rect(&writer->stack[writer->top-1].rect, rect); break; } @@ -258,12 +261,6 @@ fz_append_display_node( rect_off = size; size += SIZE_IN_NODES(sizeof(fz_rect)); } - if (path && (writer->path == NULL || path != writer->path)) - { - node.path = 1; - path_off = size; - size += SIZE_IN_NODES(sizeof(fz_path *)); - } if (color && !colorspace) { /* SoftMasks can omit a colorspace, but we know what they mean */ @@ -456,6 +453,15 @@ fz_append_display_node( size += SIZE_IN_NODES(sizeof(fz_stroke_state *)); node.stroke = 1; } + if (path && (writer->path == NULL || path != writer->path)) + { + int max = SIZE_IN_NODES(MAX_NODE_SIZE) - size - SIZE_IN_NODES(private_data_len); + path_size = SIZE_IN_NODES(fz_pack_path(ctx, NULL, max, path)); + node.path = 1; + path_off = size; + + size += path_size; + } if (private_data != NULL) { private_off = size; @@ -480,12 +486,24 @@ fz_append_display_node( if (writer->stack[i].update != NULL) writer->stack[i].update = (fz_rect *)(((char *)writer->stack[i].update) + diff); } + if (writer->path) + writer->path = (fz_path *)(((char *)writer->path) + diff); } + /* Write the node to the list */ + node.size = size; + node.flags = flags; + assert(size < (1<<9)); + node_ptr = &list->list[list->len]; + *node_ptr = node; + /* Path is the most frequent one, so try to avoid the try/catch in * this case */ if (path_off) - my_path = fz_keep_path(ctx, path); + { + my_path = (void *)(&node_ptr[path_off]); + (void)fz_pack_path(ctx, (void *)my_path, path_size * sizeof(fz_display_node), path); + } if (stroke_off) { @@ -500,12 +518,6 @@ fz_append_display_node( } } - /* Write the node to the list */ - node.size = size; - node.flags = flags; - assert(size < (1<<9)); - node_ptr = &list->list[list->len]; - *node_ptr = node; if (rect_off) { fz_rect *out_rect = (fz_rect *)(void *)(&node_ptr[rect_off]); @@ -516,8 +528,6 @@ fz_append_display_node( } if (path_off) { - fz_path **out_path = (fz_path **)(void *)(&node_ptr[path_off]); - *out_path = my_path; fz_drop_path(ctx, writer->path); writer->path = fz_keep_path(ctx, my_path); /* Can never fail */ } @@ -1282,11 +1292,6 @@ fz_drop_display_list_imp(fz_context *ctx, fz_storable *list_) { node += SIZE_IN_NODES(sizeof(fz_rect)); } - if (n.path) - { - fz_drop_path(ctx, *(fz_path **)node); - node += SIZE_IN_NODES(sizeof(fz_path *)); - } switch (n.cs) { default: @@ -1329,6 +1334,12 @@ fz_drop_display_list_imp(fz_context *ctx, fz_storable *list_) fz_drop_stroke_state(ctx, *(fz_stroke_state **)node); node += SIZE_IN_NODES(sizeof(fz_stroke_state *)); } + if (n.path) + { + int path_size = fz_packed_path_size((fz_path *)node); + fz_drop_path(ctx, (fz_path *)node); + node += SIZE_IN_NODES(path_size); + } switch(n.cmd) { case FZ_CMD_FILL_TEXT: @@ -1435,12 +1446,6 @@ fz_run_display_list(fz_context *ctx, fz_display_list *list, fz_device *dev, cons rect = *(fz_rect *)node; node += SIZE_IN_NODES(sizeof(fz_rect)); } - if (n.path) - { - fz_drop_path(ctx, path); - path = fz_keep_path(ctx, *(fz_path **)node); - node += SIZE_IN_NODES(sizeof(fz_path *)); - } if (n.cs) { int i; @@ -1541,6 +1546,12 @@ fz_run_display_list(fz_context *ctx, fz_display_list *list, fz_device *dev, cons stroke = fz_keep_stroke_state(ctx, *(fz_stroke_state **)node); node += SIZE_IN_NODES(sizeof(fz_stroke_state *)); } + if (n.path) + { + fz_drop_path(ctx, path); + path = fz_keep_path(ctx, (fz_path *)node); + node += SIZE_IN_NODES(fz_packed_path_size(path)); + } if (tile_skip_depth > 0) { diff --git a/source/fitz/path.c b/source/fitz/path.c index fed574da..450266a2 100644 --- a/source/fitz/path.c +++ b/source/fitz/path.c @@ -38,7 +38,8 @@ typedef enum fz_path_command_e struct fz_path_s { - int refs; + int8_t refs; + uint8_t packed; int cmd_len, cmd_cap; unsigned char *cmds; int coord_len, coord_cap; @@ -47,6 +48,21 @@ struct fz_path_s fz_point begin; }; +typedef struct fz_packed_path_s +{ + int8_t refs; + uint8_t packed; + uint8_t coord_len; + uint8_t cmd_len; +} fz_packed_path; + +enum +{ + FZ_PATH_UNPACKED = 0, + FZ_PATH_PACKED_FLAT = 1, + FZ_PATH_PACKED_OPEN = 2 +}; + #define LAST_CMD(path) ((path)->cmd_len > 0 ? (path)->cmds[(path)->cmd_len-1] : 0) fz_path * @@ -56,6 +72,7 @@ fz_new_path(fz_context *ctx) path = fz_malloc_struct(ctx, fz_path); path->refs = 1; + path->packed = FZ_PATH_UNPACKED; path->current.x = 0; path->current.y = 0; path->begin.x = 0; @@ -67,19 +84,112 @@ fz_new_path(fz_context *ctx) fz_path * fz_keep_path(fz_context *ctx, fz_path *path) { - if (path->refs == 1) + if (path == NULL) + return NULL; + if (path->refs == 1 && path->packed == FZ_PATH_UNPACKED) fz_trim_path(ctx, path); - return fz_keep_imp(ctx, path, &path->refs); + return fz_keep_imp8(ctx, path, &path->refs); } void fz_drop_path(fz_context *ctx, fz_path *path) { - if (fz_drop_imp(ctx, path, &path->refs)) + if (fz_drop_imp8(ctx, path, &path->refs)) { - fz_free(ctx, path->cmds); - fz_free(ctx, path->coords); - fz_free(ctx, path); + if (path->packed != FZ_PATH_PACKED_FLAT) + { + fz_free(ctx, path->cmds); + fz_free(ctx, path->coords); + } + if (path->packed == FZ_PATH_UNPACKED) + fz_free(ctx, path); + } +} + +int fz_packed_path_size(const fz_path *path) +{ + switch (path->packed) + { + case FZ_PATH_UNPACKED: + if (path->cmd_len > 255 || path->coord_len > 255) + return sizeof(fz_path); + return sizeof(fz_packed_path) + sizeof(float) * path->coord_len + sizeof(uint8_t) * path->cmd_len; + case FZ_PATH_PACKED_OPEN: + return sizeof(fz_path); + case FZ_PATH_PACKED_FLAT: + { + fz_packed_path *pack = (fz_packed_path *)path; + return sizeof(fz_packed_path) + sizeof(float) * pack->coord_len + sizeof(uint8_t) * pack->cmd_len; + } + default: + assert("This never happens" == NULL); + return 0; + } +} + +int +fz_pack_path(fz_context *ctx, uint8_t *pack_, int max, const fz_path *path) +{ + uint8_t *ptr; + int size; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Can't repack a packed path"); + + size = sizeof(fz_packed_path) + sizeof(float) * path->coord_len + sizeof(uint8_t) * path->cmd_len; + + /* If the path can't be packed flat, then pack it open */ + if (path->cmd_len > 255 || path->coord_len > 255 || size > max) + { + fz_path *pack = (fz_path *)pack_; + + if (sizeof(fz_path) > max) + fz_throw(ctx, FZ_ERROR_GENERIC, "Can't pack a path that small!"); + + if (pack != NULL) + { + pack->refs = 1; + pack->packed = FZ_PATH_PACKED_OPEN; + pack->current.x = 0; + pack->current.y = 0; + pack->begin.x = 0; + pack->begin.y = 0; + pack->coord_cap = path->coord_len; + pack->coord_len = path->coord_len; + pack->cmd_cap = path->cmd_len; + pack->cmd_len = path->cmd_len; + pack->coords = fz_malloc_array(ctx, path->coord_len, sizeof(float) * path->coord_len); + fz_try(ctx) + { + pack->cmds = fz_malloc_array(ctx, path->cmd_len, sizeof(uint8_t) * path->cmd_len); + } + fz_catch(ctx) + { + fz_free(ctx, pack->coords); + fz_rethrow(ctx); + } + memcpy(pack->coords, path->coords, sizeof(float) * path->coord_len); + memcpy(pack->cmds, path->cmds, sizeof(uint8_t) * path->cmd_len); + } + return sizeof(fz_path); + } + else + { + fz_packed_path *pack = (fz_packed_path *)pack_; + + if (pack != NULL) + { + pack->refs = 1; + pack->packed = FZ_PATH_PACKED_FLAT; + pack->cmd_len = path->cmd_len; + pack->coord_len = path->coord_len; + ptr = (uint8_t *)&pack[1]; + memcpy(ptr, path->coords, sizeof(float) * path->coord_len); + ptr += sizeof(float) * path->coord_len; + memcpy(ptr, path->cmds, sizeof(uint8_t) * path->cmd_len); + } + + return size; } } @@ -143,6 +253,9 @@ fz_currentpoint(fz_context *ctx, fz_path *path) void fz_moveto(fz_context *ctx, fz_path *path, float x, float y) { + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + if (path->cmd_len > 0 && LAST_CMD(path) == FZ_MOVETO) { /* Collapse moveto followed by moveto. */ @@ -163,8 +276,13 @@ fz_moveto(fz_context *ctx, fz_path *path, float x, float y) void fz_lineto(fz_context *ctx, fz_path *path, float x, float y) { - float x0 = path->current.x; - float y0 = path->current.y; + float x0, y0; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + + x0 = path->current.x; + y0 = path->current.y; if (path->cmd_len == 0) { @@ -208,8 +326,13 @@ fz_curveto(fz_context *ctx, fz_path *path, float x2, float y2, float x3, float y3) { - float x0 = path->current.x; - float y0 = path->current.y; + float x0, y0; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + + x0 = path->current.x; + y0 = path->current.y; if (path->cmd_len == 0) { @@ -260,8 +383,13 @@ fz_quadto(fz_context *ctx, fz_path *path, float x1, float y1, float x2, float y2) { - float x0 = path->current.x; - float y0 = path->current.y; + float x0, y0; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + + x0 = path->current.x; + y0 = path->current.y; if (path->cmd_len == 0) { @@ -287,8 +415,13 @@ fz_quadto(fz_context *ctx, fz_path *path, void fz_curvetov(fz_context *ctx, fz_path *path, float x2, float y2, float x3, float y3) { - float x0 = path->current.x; - float y0 = path->current.y; + float x0, y0; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + + x0 = path->current.x; + y0 = path->current.y; if (path->cmd_len == 0) { @@ -319,8 +452,13 @@ fz_curvetov(fz_context *ctx, fz_path *path, float x2, float y2, float x3, float void fz_curvetoy(fz_context *ctx, fz_path *path, float x1, float y1, float x3, float y3) { - float x0 = path->current.x; - float y0 = path->current.y; + float x0, y0; + + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + + x0 = path->current.x; + y0 = path->current.y; if (path->cmd_len == 0) { @@ -348,6 +486,9 @@ fz_closepath(fz_context *ctx, fz_path *path) { uint8_t rep; + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + if (path->cmd_len == 0) { fz_warn(ctx, "closepath with no current point"); @@ -410,6 +551,9 @@ fz_closepath(fz_context *ctx, fz_path *path) void fz_rectto(fz_context *ctx, fz_path *path, float x1, float y1, float x2, float y2) { + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot modify a packed path"); + if (path->cmd_len > 0 && LAST_CMD(path) == FZ_MOVETO) { /* Collapse moveto followed by rectto. */ @@ -435,27 +579,47 @@ static inline fz_rect *bound_expand(fz_rect *r, const fz_point *p) void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, const fz_path *path) { - int i, k; + int i, k, cmd_len; float x, y, sx, sy; + uint8_t *cmds = path->cmds; + float *coords = path->coords; - if (path->cmd_len == 0) + switch (path->packed) + { + case FZ_PATH_UNPACKED: + case FZ_PATH_PACKED_OPEN: + cmd_len = path->cmd_len; + coords = path->coords; + cmds = path->cmds; + break; + case FZ_PATH_PACKED_FLAT: + cmd_len = ((fz_packed_path *)path)->cmd_len; + coords = (float *)&((fz_packed_path *)path)[1]; + cmds = (uint8_t *)&coords[((fz_packed_path *)path)->coord_len]; + break; + default: + assert("This never happens" == NULL); return; + } - for (k=0, i = 0; i < path->cmd_len; i++) + if (cmd_len == 0) + return; + + for (k=0, i = 0; i < cmd_len; i++) { - uint8_t cmd = path->cmds[i]; + uint8_t cmd = cmds[i]; switch (cmd) { case FZ_CURVETO: case FZ_CURVETOCLOSE: proc->curveto(ctx, arg, - path->coords[k], - path->coords[k+1], - path->coords[k+2], - path->coords[k+3], - x = path->coords[k+4], - y = path->coords[k+5]); + coords[k], + coords[k+1], + coords[k+2], + coords[k+3], + x = coords[k+4], + y = coords[k+5]); k += 6; if (cmd == FZ_CURVETOCLOSE) { @@ -469,21 +633,21 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_CURVETOVCLOSE: if (proc->curvetov) proc->curvetov(ctx, arg, - path->coords[k], - path->coords[k+1], - x = path->coords[k+2], - y = path->coords[k+3]); + coords[k], + coords[k+1], + x = coords[k+2], + y = coords[k+3]); else { proc->curveto(ctx, arg, x, y, - path->coords[k], - path->coords[k+1], - path->coords[k+2], - path->coords[k+3]); - x = path->coords[k+2]; - y = path->coords[k+3]; + coords[k], + coords[k+1], + coords[k+2], + coords[k+3]); + x = coords[k+2]; + y = coords[k+3]; } k += 4; if (cmd == FZ_CURVETOVCLOSE) @@ -498,18 +662,18 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_CURVETOYCLOSE: if (proc->curvetoy) proc->curvetoy(ctx, arg, - path->coords[k], - path->coords[k+1], - x = path->coords[k+2], - y = path->coords[k+3]); + coords[k], + coords[k+1], + x = coords[k+2], + y = coords[k+3]); else proc->curveto(ctx, arg, - path->coords[k], - path->coords[k+1], - path->coords[k+2], - path->coords[k+3], - x = path->coords[k+2], - y = path->coords[k+3]); + coords[k], + coords[k+1], + coords[k+2], + coords[k+3], + x = coords[k+2], + y = coords[k+3]); k += 4; if (cmd == FZ_CURVETOYCLOSE) { @@ -523,18 +687,18 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_QUADTOCLOSE: if (proc->quadto) proc->quadto(ctx, arg, - path->coords[k], - path->coords[k+1], - x = path->coords[k+2], - y = path->coords[k+3]); + coords[k], + coords[k+1], + x = coords[k+2], + y = coords[k+3]); else { - float c2x = path->coords[k] * 2; - float c2y = path->coords[k+1] * 2; + float c2x = coords[k] * 2; + float c2y = coords[k+1] * 2; float c1x = (x + c2x) / 3; float c1y = (y + c2y) / 3; - x = path->coords[k+2]; - y = path->coords[k+3]; + x = coords[k+2]; + y = coords[k+3]; c2x = (c2x + x) / 3; c2y = (c2y + y) / 3; @@ -558,8 +722,8 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_MOVETO: case FZ_MOVETOCLOSE: proc->moveto(ctx, arg, - x = path->coords[k], - y = path->coords[k+1]); + x = coords[k], + y = coords[k+1]); k += 2; sx = x; sy = y; @@ -574,8 +738,8 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_LINETO: case FZ_LINETOCLOSE: proc->lineto(ctx, arg, - x = path->coords[k], - y = path->coords[k+1]); + x = coords[k], + y = coords[k+1]); k += 2; if (cmd == FZ_LINETOCLOSE) { @@ -588,7 +752,7 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_HORIZTO: case FZ_HORIZTOCLOSE: proc->lineto(ctx, arg, - x = path->coords[k], + x = coords[k], y); k += 1; if (cmd == FZ_HORIZTOCLOSE) @@ -603,7 +767,7 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, case FZ_VERTTOCLOSE: proc->lineto(ctx, arg, x, - y = path->coords[k]); + y = coords[k]); k += 1; if (cmd == FZ_VERTTOCLOSE) { @@ -630,25 +794,25 @@ void fz_process_path(fz_context *ctx, const fz_path_processor *proc, void *arg, if (proc->rectto) { proc->rectto(ctx, arg, - x = path->coords[k], - y = path->coords[k+1], - path->coords[k+2], - path->coords[k+3]); + x = coords[k], + y = coords[k+1], + coords[k+2], + coords[k+3]); } else { proc->moveto(ctx, arg, - x = path->coords[k], - y = path->coords[k+1]); + x = coords[k], + y = coords[k+1]); proc->lineto(ctx, arg, - path->coords[k+2], - path->coords[k+1]); + coords[k+2], + coords[k+1]); proc->lineto(ctx, arg, - path->coords[k+2], - path->coords[k+3]); + coords[k+2], + coords[k+3]); proc->lineto(ctx, arg, - path->coords[k], - path->coords[k+3]); + coords[k], + coords[k+3]); if (proc->close) proc->close(ctx, arg); } @@ -792,6 +956,9 @@ fz_transform_path(fz_context *ctx, fz_path *path, const fz_matrix *ctm) int i, k, n; fz_point p, p1, p2, p3, q, s; + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Cannot transform a packed path"); + if (ctm->b == 0 && ctm->c == 0) { /* Simple, in place transform */ @@ -1158,6 +1325,8 @@ fz_transform_path(fz_context *ctx, fz_path *path, const fz_matrix *ctm) void fz_trim_path(fz_context *ctx, fz_path *path) { + if (path->packed) + fz_throw(ctx, FZ_ERROR_GENERIC, "Can't trim a packed path"); if (path->cmd_cap > path->cmd_len) { path->cmds = fz_resize_array(ctx, path->cmds, path->cmd_len, sizeof(unsigned char)); |