Thu, 13 Mar 2003 07:59:10 +0000
don't use page mode USE_OUTLINES if there are no outline entries.
eric@80 | 1 | /* |
eric@80 | 2 | * t2p: Create a PDF file from the contents of one or more TIFF |
eric@80 | 3 | * bilevel image files. The images in the resulting PDF file |
eric@80 | 4 | * will be compressed using ITU-T T.6 (G4) fax encoding. |
eric@80 | 5 | * |
eric@80 | 6 | * PDF routines |
eric@113 | 7 | * $Id: pdf_name_tree.c,v 1.8 2003/03/12 03:13:28 eric Exp $ |
eric@80 | 8 | * Copyright 2003 Eric Smith <eric@brouhaha.com> |
eric@80 | 9 | * |
eric@80 | 10 | * This program is free software; you can redistribute it and/or modify |
eric@80 | 11 | * it under the terms of the GNU General Public License version 2 as |
eric@80 | 12 | * published by the Free Software Foundation. Note that permission is |
eric@80 | 13 | * not granted to redistribute this program under the terms of any |
eric@80 | 14 | * other version of the General Public License. |
eric@80 | 15 | * |
eric@80 | 16 | * This program is distributed in the hope that it will be useful, |
eric@80 | 17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
eric@80 | 18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
eric@80 | 19 | * GNU General Public License for more details. |
eric@80 | 20 | * |
eric@80 | 21 | * You should have received a copy of the GNU General Public License |
eric@80 | 22 | * along with this program; if not, write to the Free Software |
eric@80 | 23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA |
eric@80 | 24 | */ |
eric@80 | 25 | |
eric@80 | 26 | |
eric@80 | 27 | #include <stdbool.h> |
eric@80 | 28 | #include <stdint.h> |
eric@80 | 29 | #include <stdio.h> |
eric@80 | 30 | #include <stdlib.h> |
eric@80 | 31 | #include <string.h> |
eric@80 | 32 | |
eric@80 | 33 | |
eric@80 | 34 | #include "bitblt.h" |
eric@80 | 35 | #include "pdf.h" |
eric@80 | 36 | #include "pdf_util.h" |
eric@80 | 37 | #include "pdf_prim.h" |
eric@80 | 38 | #include "pdf_private.h" |
eric@80 | 39 | #include "pdf_name_tree.h" |
eric@80 | 40 | |
eric@80 | 41 | |
eric@80 | 42 | #define MAX_NAME_TREE_NODE_ENTRIES 16 |
eric@80 | 43 | |
eric@80 | 44 | |
eric@80 | 45 | struct pdf_name_tree_node |
eric@80 | 46 | { |
eric@80 | 47 | struct pdf_obj *dict; /* indirect reference */ |
eric@80 | 48 | |
eric@80 | 49 | struct pdf_name_tree_node *parent; /* NULL for root */ |
eric@80 | 50 | bool leaf; |
eric@80 | 51 | |
eric@80 | 52 | int count; /* how many kids or names/numbers are |
eric@80 | 53 | attached to this node */ |
eric@80 | 54 | |
eric@80 | 55 | struct pdf_name_tree_node *kids [MAX_NAME_TREE_NODE_ENTRIES]; /* non-leaf only */ |
eric@80 | 56 | |
eric@80 | 57 | struct pdf_obj *min_key; |
eric@80 | 58 | struct pdf_obj *max_key; |
eric@80 | 59 | |
eric@80 | 60 | /* following fields valid in leaf nodes only: */ |
eric@80 | 61 | |
eric@80 | 62 | struct pdf_obj *keys [MAX_NAME_TREE_NODE_ENTRIES]; |
eric@80 | 63 | struct pdf_obj *values [MAX_NAME_TREE_NODE_ENTRIES]; |
eric@80 | 64 | }; |
eric@80 | 65 | |
eric@80 | 66 | |
eric@80 | 67 | struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file, |
eric@80 | 68 | bool number_tree) |
eric@80 | 69 | { |
eric@80 | 70 | struct pdf_name_tree *tree; |
eric@80 | 71 | struct pdf_name_tree_node *root; |
eric@80 | 72 | |
eric@80 | 73 | root = pdf_calloc (1, sizeof (struct pdf_name_tree_node)); |
eric@80 | 74 | tree = pdf_calloc (1, sizeof (struct pdf_name_tree)); |
eric@80 | 75 | |
eric@80 | 76 | tree->pdf_file = pdf_file; |
eric@80 | 77 | tree->root = root; |
eric@80 | 78 | tree->number_tree = number_tree; |
eric@80 | 79 | |
eric@80 | 80 | root->parent = NULL; |
eric@80 | 81 | root->leaf = 1; |
eric@80 | 82 | |
eric@85 | 83 | tree->next = pdf_file->name_tree_list; |
eric@85 | 84 | pdf_file->name_tree_list = tree; |
eric@85 | 85 | |
eric@80 | 86 | return (tree); |
eric@80 | 87 | } |
eric@80 | 88 | |
eric@80 | 89 | |
eric@80 | 90 | static void pdf_split_name_tree_node (struct pdf_name_tree *tree, |
eric@80 | 91 | struct pdf_name_tree_node *node) |
eric@80 | 92 | { |
eric@87 | 93 | struct pdf_name_tree_node *parent; |
eric@80 | 94 | struct pdf_name_tree_node *new_node; |
eric@87 | 95 | int i, j; |
eric@80 | 96 | |
eric@87 | 97 | parent = node->parent; |
eric@87 | 98 | if (! parent) |
eric@80 | 99 | { |
eric@80 | 100 | /* create new root above current root */ |
eric@80 | 101 | struct pdf_name_tree_node *new_root_node; |
eric@80 | 102 | |
eric@80 | 103 | new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node)); |
eric@80 | 104 | |
eric@80 | 105 | new_root_node->parent = NULL; |
eric@80 | 106 | new_root_node->leaf = 0; |
eric@80 | 107 | |
eric@80 | 108 | new_root_node->count = 1; |
eric@80 | 109 | new_root_node->kids [0] = node; |
eric@80 | 110 | |
eric@80 | 111 | new_root_node->min_key = node->min_key; |
eric@80 | 112 | new_root_node->max_key = node->max_key; |
eric@80 | 113 | |
eric@87 | 114 | parent = new_root_node; |
eric@80 | 115 | node->parent = new_root_node; |
eric@80 | 116 | tree->root = new_root_node; |
eric@80 | 117 | } |
eric@80 | 118 | |
eric@89 | 119 | if (parent->count == MAX_NAME_TREE_NODE_ENTRIES) |
eric@89 | 120 | { |
eric@89 | 121 | pdf_split_name_tree_node (tree, parent); |
eric@89 | 122 | parent = node->parent; |
eric@89 | 123 | } |
eric@89 | 124 | |
eric@80 | 125 | new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node)); |
eric@87 | 126 | new_node->parent = parent; |
eric@80 | 127 | new_node->leaf = node->leaf; |
eric@84 | 128 | |
eric@87 | 129 | /* move half the node's entries into the new node */ |
eric@87 | 130 | i = node->count / 2; |
eric@87 | 131 | j = node->count - i; |
eric@87 | 132 | |
eric@87 | 133 | memcpy (& new_node->kids [0], |
eric@87 | 134 | & node->kids [i], |
eric@87 | 135 | j * sizeof (struct pdf_name_tree_node *)); |
eric@87 | 136 | memcpy (& new_node->keys [0], |
eric@87 | 137 | & node->keys [i], |
eric@87 | 138 | j * sizeof (struct pdf_obj *)); |
eric@87 | 139 | memcpy (& new_node->values [0], |
eric@87 | 140 | & node->values [i], |
eric@87 | 141 | j * sizeof (struct pdf_obj *)); |
eric@89 | 142 | |
eric@87 | 143 | node->count = i; |
eric@87 | 144 | new_node->count = j; |
eric@87 | 145 | |
eric@89 | 146 | if (! new_node->leaf) |
eric@89 | 147 | for (i = 0; i < j; i++) |
eric@89 | 148 | new_node->kids [i]->parent = new_node; |
eric@89 | 149 | |
eric@87 | 150 | /* set max_key of the old node */ |
eric@87 | 151 | if (node->leaf) |
eric@87 | 152 | node->max_key = node->keys [node->count - 1]; |
eric@87 | 153 | else |
eric@87 | 154 | node->max_key = node->kids [node->count - 1]->max_key; |
eric@87 | 155 | |
eric@87 | 156 | /* set min_key and max_key in the new node */ |
eric@87 | 157 | if (new_node->leaf) |
eric@87 | 158 | { |
eric@87 | 159 | new_node->min_key = new_node->keys [0]; |
eric@87 | 160 | new_node->max_key = new_node->keys [new_node->count - 1]; |
eric@87 | 161 | } |
eric@87 | 162 | else |
eric@87 | 163 | { |
eric@87 | 164 | new_node->min_key = new_node->kids [0]->min_key; |
eric@87 | 165 | new_node->max_key = new_node->kids [new_node->count - 1]->max_key; |
eric@87 | 166 | } |
eric@87 | 167 | |
eric@87 | 168 | /* insert new node in parent's kids array */ |
eric@87 | 169 | /* find entry of old node */ |
eric@87 | 170 | for (i = 0; i < parent->count; i++) |
eric@87 | 171 | if (parent->kids [i] == node) |
eric@87 | 172 | break; |
eric@87 | 173 | |
eric@87 | 174 | /* it had better have been there! */ |
eric@87 | 175 | pdf_assert (i < parent->count); |
eric@87 | 176 | |
eric@87 | 177 | /* the new node goes in the slot to the right of the old node */ |
eric@87 | 178 | i++; |
eric@87 | 179 | |
eric@87 | 180 | /* move other entries right one position */ |
eric@88 | 181 | if (i != parent->count) |
eric@87 | 182 | { |
eric@87 | 183 | memmove (& parent->kids [i+1], |
eric@87 | 184 | & parent->kids [i], |
eric@87 | 185 | (parent->count - i) * sizeof (struct pdf_name_tree_node *)); |
eric@87 | 186 | } |
eric@87 | 187 | |
eric@87 | 188 | parent->kids [i] = new_node; |
eric@87 | 189 | parent->count++; |
eric@80 | 190 | } |
eric@80 | 191 | |
eric@80 | 192 | |
eric@80 | 193 | static void pdf_add_tree_element (struct pdf_name_tree *tree, |
eric@80 | 194 | struct pdf_obj *key, |
eric@80 | 195 | struct pdf_obj *val) |
eric@80 | 196 | { |
eric@80 | 197 | struct pdf_name_tree_node *node; |
eric@83 | 198 | int i; |
eric@80 | 199 | |
eric@80 | 200 | /* find node which should contain element */ |
eric@80 | 201 | node = tree->root; |
eric@83 | 202 | while (! node->leaf) |
eric@83 | 203 | { |
eric@83 | 204 | for (i = 0; i < (node->count - 1); i++) |
eric@83 | 205 | if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0) |
eric@83 | 206 | break; |
eric@83 | 207 | node = node->kids [i]; |
eric@83 | 208 | } |
eric@80 | 209 | |
eric@80 | 210 | /* if node is full, split, recursing to root if necessary */ |
eric@80 | 211 | if (node->count == MAX_NAME_TREE_NODE_ENTRIES) |
eric@80 | 212 | { |
eric@80 | 213 | pdf_split_name_tree_node (tree, node); |
eric@80 | 214 | pdf_add_tree_element (tree, key, val); |
eric@80 | 215 | return; |
eric@80 | 216 | } |
eric@83 | 217 | |
eric@84 | 218 | /* figure out in which slot to insert it */ |
eric@84 | 219 | for (i = 0; i < node->count; i++) |
eric@88 | 220 | if (pdf_compare_obj (key, node->keys [i]) < 0) |
eric@84 | 221 | break; |
eric@84 | 222 | |
eric@84 | 223 | /* move other entries right one position */ |
eric@84 | 224 | if (i != node->count) |
eric@84 | 225 | { |
eric@84 | 226 | memmove (& node->keys [i+1], |
eric@84 | 227 | & node->keys [i], |
eric@84 | 228 | (node->count - i) * sizeof (struct pdf_obj *)); |
eric@84 | 229 | memmove (& node->values [i+1], |
eric@84 | 230 | & node->values [i], |
eric@84 | 231 | (node->count - i) * sizeof (struct pdf_obj *)); |
eric@84 | 232 | } |
eric@84 | 233 | |
eric@84 | 234 | node->keys [i] = key; |
eric@84 | 235 | node->values [i] = val; |
eric@84 | 236 | |
eric@84 | 237 | node->count++; |
eric@83 | 238 | |
eric@83 | 239 | /* update limits, recursing upwards if necessary */ |
eric@83 | 240 | if (i == 0) |
eric@83 | 241 | { |
eric@83 | 242 | node->min_key = key; |
eric@83 | 243 | while (node->parent && (node->parent->kids [0] == node)) |
eric@83 | 244 | { |
eric@83 | 245 | node = node->parent; |
eric@83 | 246 | node->min_key = key; |
eric@83 | 247 | } |
eric@83 | 248 | } |
eric@88 | 249 | if (i == (node->count - 1)) |
eric@83 | 250 | { |
eric@83 | 251 | node->max_key = key; |
eric@83 | 252 | while (node->parent && (node->parent->kids [node->parent->count - 1] == node)) |
eric@83 | 253 | { |
eric@83 | 254 | node = node->parent; |
eric@83 | 255 | node->max_key = key; |
eric@83 | 256 | } |
eric@83 | 257 | } |
eric@80 | 258 | } |
eric@80 | 259 | |
eric@80 | 260 | |
eric@80 | 261 | void pdf_add_name_tree_element (struct pdf_name_tree *tree, |
eric@80 | 262 | char *key, |
eric@80 | 263 | struct pdf_obj *val) |
eric@80 | 264 | { |
eric@80 | 265 | struct pdf_obj *key_obj = pdf_new_string (key); |
eric@80 | 266 | pdf_add_tree_element (tree, key_obj, val); |
eric@80 | 267 | } |
eric@80 | 268 | |
eric@80 | 269 | |
eric@80 | 270 | void pdf_add_number_tree_element (struct pdf_name_tree *tree, |
eric@80 | 271 | long key, |
eric@80 | 272 | struct pdf_obj *val) |
eric@80 | 273 | { |
eric@80 | 274 | struct pdf_obj *key_obj = pdf_new_integer (key); |
eric@80 | 275 | pdf_add_tree_element (tree, key_obj, val); |
eric@80 | 276 | } |
eric@80 | 277 | |
eric@80 | 278 | |
eric@80 | 279 | static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree, |
eric@80 | 280 | struct pdf_name_tree_node *node) |
eric@80 | 281 | { |
eric@80 | 282 | int i; |
eric@80 | 283 | |
eric@80 | 284 | node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY)); |
eric@80 | 285 | |
eric@80 | 286 | if (node->leaf) |
eric@80 | 287 | { |
eric@80 | 288 | /* write Names or Nums array */ |
eric@80 | 289 | struct pdf_obj *names = pdf_new_obj (PT_ARRAY); |
eric@80 | 290 | for (i = 0; i < node->count; i++) |
eric@80 | 291 | { |
eric@80 | 292 | pdf_add_array_elem (names, node->keys [i]); |
eric@80 | 293 | pdf_add_array_elem (names, node->values [i]); |
eric@80 | 294 | } |
eric@80 | 295 | pdf_set_dict_entry (node->dict, |
eric@80 | 296 | tree->number_tree ? "Nums" : "Names", |
eric@80 | 297 | names); |
eric@80 | 298 | } |
eric@80 | 299 | else |
eric@80 | 300 | { |
eric@80 | 301 | /* finalize the children first so that their dict ind ref is |
eric@80 | 302 | available */ |
eric@113 | 303 | struct pdf_obj *kids; |
eric@113 | 304 | |
eric@80 | 305 | for (i = 0; i < node->count; i++) |
eric@80 | 306 | pdf_finalize_name_tree_node (tree, node->kids [i]); |
eric@80 | 307 | |
eric@80 | 308 | /* write Kids array */ |
eric@113 | 309 | kids = pdf_new_obj (PT_ARRAY); |
eric@80 | 310 | for (i = 0; i < node->count; i++) |
eric@80 | 311 | pdf_add_array_elem (kids, node->kids [i]->dict); |
eric@80 | 312 | pdf_set_dict_entry (node->dict, "Kids", kids); |
eric@80 | 313 | } |
eric@80 | 314 | |
eric@88 | 315 | if (node->parent) |
eric@80 | 316 | { |
eric@80 | 317 | /* write Limits array */ |
eric@80 | 318 | struct pdf_obj *limits = pdf_new_obj (PT_ARRAY); |
eric@80 | 319 | pdf_add_array_elem (limits, node->min_key); |
eric@80 | 320 | pdf_add_array_elem (limits, node->max_key); |
eric@80 | 321 | pdf_set_dict_entry (node->dict, "Limits", limits); |
eric@80 | 322 | } |
eric@80 | 323 | } |
eric@80 | 324 | |
eric@80 | 325 | |
eric@85 | 326 | void pdf_finalize_name_trees (pdf_file_handle pdf_file) |
eric@80 | 327 | { |
eric@85 | 328 | struct pdf_name_tree *tree; |
eric@85 | 329 | |
eric@85 | 330 | for (tree = pdf_file->name_tree_list; tree; tree = tree->next) |
eric@85 | 331 | pdf_finalize_name_tree_node (tree, tree->root); |
eric@80 | 332 | } |