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