Update sds library to commit 14b8e8a1.
[ttfautohint.git] / lib / tadeltas.c
blobc5b92fb5a87da34984ec127e274be23ba77079ad
1 /* tadeltas.c */
3 /*
4 * Copyright (C) 2014 by Werner Lemberg.
6 * This file is part of the ttfautohint library, and may only be used,
7 * modified, and distributed under the terms given in `COPYING'. By
8 * continuing to use, modify, or distribute this file you indicate that you
9 * have read `COPYING' and understand and accept it fully.
11 * The file `COPYING' mentioned in the previous paragraph is distributed
12 * with the ttfautohint library.
15 #include "ta.h"
17 #include <locale.h>
18 #include <errno.h>
19 #include <ctype.h>
20 #include <math.h>
21 #include <stdbool.h> /* for llrb.h */
23 #include "llrb.h" /* a red-black tree implementation */
24 #include "tadeltas-bison.h"
26 Deltas*
27 TA_deltas_new(long font_idx,
28 long glyph_idx,
29 number_range* point_set,
30 double x_shift,
31 double y_shift,
32 number_range* ppem_set)
34 Deltas* deltas;
37 deltas = (Deltas*)malloc(sizeof (Deltas));
38 if (!deltas)
39 return NULL;
41 deltas->font_idx = font_idx;
42 deltas->glyph_idx = glyph_idx;
43 deltas->points = number_set_reverse(point_set);
45 /* we round shift values to multiples of 1/(2^DELTA_SHIFT) */
46 deltas->x_shift = (char)(x_shift * DELTA_FACTOR
47 + (x_shift > 0 ? 0.5 : -0.5));
48 deltas->y_shift = (char)(y_shift * DELTA_FACTOR
49 + (y_shift > 0 ? 0.5 : -0.5));
51 deltas->ppems = number_set_reverse(ppem_set);
52 deltas->next = NULL;
54 return deltas;
58 Deltas*
59 TA_deltas_prepend(Deltas* list,
60 Deltas* element)
62 if (!element)
63 return list;
65 element->next = list;
67 return element;
71 Deltas*
72 TA_deltas_reverse(Deltas* list)
74 Deltas* cur;
77 cur = list;
78 list = NULL;
80 while (cur)
82 Deltas* tmp;
85 tmp = cur;
86 cur = cur->next;
87 tmp->next = list;
88 list = tmp;
91 return list;
95 void
96 TA_deltas_free(Deltas* deltas)
98 while (deltas)
100 Deltas* tmp;
103 number_set_free(deltas->points);
104 number_set_free(deltas->ppems);
106 tmp = deltas;
107 deltas = deltas->next;
108 free(tmp);
114 deltas_show_line(FONT* font,
115 Deltas* deltas)
117 char glyph_name_buf[64];
118 char* points_buf = NULL;
119 char* ppems_buf = NULL;
121 sds s;
123 FT_Face face;
126 s = sdsempty();
127 if (!s)
128 return NULL;
130 if (!deltas)
131 goto Exit;
133 if (deltas->font_idx >= font->num_sfnts)
134 goto Exit;
136 face = font->sfnts[deltas->font_idx].face;
137 glyph_name_buf[0] = '\0';
138 if (FT_HAS_GLYPH_NAMES(face))
139 FT_Get_Glyph_Name(face, deltas->glyph_idx, glyph_name_buf, 64);
141 points_buf = number_set_show(deltas->points, -1, -1);
142 if (!points_buf)
143 goto Exit;
144 ppems_buf = number_set_show(deltas->ppems, -1, -1);
145 if (!ppems_buf)
146 goto Exit;
148 /* display glyph index if we don't have a glyph name */
149 if (*glyph_name_buf)
150 s = sdscatprintf(s, "%ld %s p %s x %.20g y %.20g @ %s",
151 deltas->font_idx,
152 glyph_name_buf,
153 points_buf,
154 (double)deltas->x_shift / DELTA_FACTOR,
155 (double)deltas->y_shift / DELTA_FACTOR,
156 ppems_buf);
157 else
158 s = sdscatprintf(s, "%ld %ld p %s x %.20g y %.20g @ %s",
159 deltas->font_idx,
160 deltas->glyph_idx,
161 points_buf,
162 (double)deltas->x_shift / DELTA_FACTOR,
163 (double)deltas->y_shift / DELTA_FACTOR,
164 ppems_buf);
166 Exit:
167 free(points_buf);
168 free(ppems_buf);
170 return s;
174 char*
175 TA_deltas_show(FONT* font)
177 sds s;
178 size_t len;
179 char* res;
181 Deltas* deltas = font->deltas;
184 s = sdsempty();
185 if (!s)
186 return NULL;
188 while (deltas)
190 sds d;
193 /* append current line to buffer, followed by a newline character */
194 d = deltas_show_line(font, deltas);
195 if (!d)
197 sdsfree(s);
198 return NULL;
200 s = sdscatsds(s, d);
201 sdsfree(d);
202 if (!s)
203 return NULL;
204 s = sdscat(s, "\n");
205 if (!s)
206 return NULL;
208 deltas = deltas->next;
211 /* we return an empty string if there is no data */
212 len = sdslen(s) + 1;
213 res = (char*)malloc(len);
214 if (res)
215 memcpy(res, s, len);
217 sdsfree(s);
219 return res;
223 /* Parse delta exceptions in `font->deltas_buf'. */
225 TA_Error
226 TA_deltas_parse_buffer(FONT* font,
227 char** error_string_p,
228 unsigned int* errlinenum_p,
229 char** errline_p,
230 char** errpos_p)
232 int bison_error;
234 Deltas_Context context;
237 /* nothing to do if no data */
238 if (!font->deltas_buf)
240 font->deltas = NULL;
241 return TA_Err_Ok;
244 TA_deltas_scanner_init(&context, font);
245 if (context.error)
246 goto Fail;
247 /* this is `yyparse' in disguise */
248 bison_error = TA_deltas_parse(&context);
249 TA_deltas_scanner_done(&context);
251 if (bison_error)
253 if (bison_error == 2)
254 context.error = TA_Err_Deltas_Allocation_Error;
256 Fail:
257 font->deltas = NULL;
259 if (context.error == TA_Err_Deltas_Allocation_Error
260 || context.error == TA_Err_Deltas_Flex_Error)
262 *errlinenum_p = 0;
263 *errline_p = NULL;
264 *errpos_p = NULL;
265 if (context.errmsg)
266 *error_string_p = strdup(context.errmsg);
267 else
268 *error_string_p = strdup(TA_get_error_message(context.error));
270 else
272 int i, ret;
273 char auxbuf[128];
275 char* buf_end;
276 char* p_start;
277 char* p_end;
280 /* construct data for `errline_p' */
281 buf_end = font->deltas_buf + font->deltas_len;
283 p_start = font->deltas_buf;
284 if (context.errline_num > 1)
286 i = 1;
287 while (p_start < buf_end)
289 if (*p_start++ == '\n')
291 i++;
292 if (i == context.errline_num)
293 break;
298 p_end = p_start;
299 while (p_end < buf_end)
301 if (*p_end == '\n')
302 break;
303 p_end++;
305 *errline_p = strndup(p_start, p_end - p_start);
307 /* construct data for `error_string_p' */
308 if (context.error == TA_Err_Deltas_Invalid_Font_Index)
309 sprintf(auxbuf, " (valid range is [%ld;%ld])",
311 font->num_sfnts);
312 else if (context.error == TA_Err_Deltas_Invalid_Glyph_Index)
313 sprintf(auxbuf, " (valid range is [%ld;%ld])",
315 font->sfnts[context.font_idx].face->num_glyphs);
316 else if (context.error == TA_Err_Deltas_Invalid_Shift)
317 sprintf(auxbuf, " (valid interval is [%g;%g])",
318 DELTA_SHIFT_MIN,
319 DELTA_SHIFT_MAX);
320 else if (context.error == TA_Err_Deltas_Invalid_Range)
321 sprintf(auxbuf, " (values must be within [%ld;%ld])",
322 context.number_set_min,
323 context.number_set_max);
324 else
325 auxbuf[0] = '\0';
327 ret = asprintf(error_string_p, "%s%s",
328 *context.errmsg ? context.errmsg
329 : TA_get_error_message(context.error),
330 auxbuf);
331 if (ret == -1)
332 *error_string_p = NULL;
334 if (errline_p)
335 *errpos_p = *errline_p + context.errline_pos_left - 1;
336 else
337 *errpos_p = NULL;
339 *errlinenum_p = context.errline_num;
342 else
343 font->deltas = context.result;
345 return context.error;
349 /* node structure for delta exception data */
351 typedef struct Node Node;
352 struct Node
354 LLRB_ENTRY(Node) entry;
355 Delta delta;
359 /* comparison function for our red-black tree */
361 static int
362 nodecmp(Node* e1,
363 Node* e2)
365 long diff;
368 /* sort by font index ... */
369 diff = e1->delta.font_idx - e2->delta.font_idx;
370 if (diff)
371 goto Exit;
373 /* ... then by glyph index ... */
374 diff = e1->delta.glyph_idx - e2->delta.glyph_idx;
375 if (diff)
376 goto Exit;
378 /* ... then by ppem ... */
379 diff = e1->delta.ppem - e2->delta.ppem;
380 if (diff)
381 goto Exit;
383 /* ... then by point index */
384 diff = e1->delta.point_idx - e2->delta.point_idx;
386 Exit:
387 /* https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign */
388 return (diff > 0) - (diff < 0);
392 /* the red-black tree function body */
393 typedef struct deltas_data deltas_data;
395 LLRB_HEAD(deltas_data, Node);
397 /* no trailing semicolon in the next line */
398 LLRB_GENERATE_STATIC(deltas_data, Node, entry, nodecmp)
401 void
402 TA_deltas_free_tree(FONT* font)
404 deltas_data* deltas_data_head = (deltas_data*)font->deltas_data_head;
406 Node* node;
407 Node* next_node;
410 if (!deltas_data_head)
411 return;
413 for (node = LLRB_MIN(deltas_data, deltas_data_head);
414 node;
415 node = next_node)
417 next_node = LLRB_NEXT(deltas_data, deltas_data_head, node);
418 LLRB_REMOVE(deltas_data, deltas_data_head, node);
419 free(node);
422 free(deltas_data_head);
426 TA_Error
427 TA_deltas_build_tree(FONT* font)
429 Deltas* deltas = font->deltas;
430 deltas_data* deltas_data_head;
431 int emit_newline = 0;
434 /* nothing to do if no data */
435 if (!deltas)
437 font->deltas_data_head = NULL;
438 return TA_Err_Ok;
441 deltas_data_head = (deltas_data*)malloc(sizeof (deltas_data));
442 if (!deltas_data_head)
443 return FT_Err_Out_Of_Memory;
445 LLRB_INIT(deltas_data_head);
447 while (deltas)
449 long font_idx = deltas->font_idx;
450 long glyph_idx = deltas->glyph_idx;
451 char x_shift = deltas->x_shift;
452 char y_shift = deltas->y_shift;
454 number_set_iter ppems_iter;
455 int ppem;
458 ppems_iter.range = deltas->ppems;
459 ppem = number_set_get_first(&ppems_iter);
461 while (ppems_iter.range)
463 number_set_iter points_iter;
464 int point_idx;
467 points_iter.range = deltas->points;
468 point_idx = number_set_get_first(&points_iter);
470 while (points_iter.range)
472 Node* node;
473 Node* val;
476 node = (Node*)malloc(sizeof (Node));
477 if (!node)
478 return FT_Err_Out_Of_Memory;
480 node->delta.font_idx = font_idx;
481 node->delta.glyph_idx = glyph_idx;
482 node->delta.ppem = ppem;
483 node->delta.point_idx = point_idx;
484 node->delta.x_shift = x_shift;
485 node->delta.y_shift = y_shift;
487 val = LLRB_INSERT(deltas_data, deltas_data_head, node);
488 if (val)
489 free(node);
490 if (val && font->debug)
492 /* entry is already present; we ignore it */
493 Deltas d;
494 number_range ppems;
495 number_range points;
497 sds s;
500 /* construct Deltas entry for debugging output */
501 ppems.start = ppem;
502 ppems.end = ppem;
503 ppems.next = NULL;
504 points.start = point_idx;
505 points.end = point_idx;
506 points.next = NULL;
508 d.font_idx = font_idx;
509 d.glyph_idx = glyph_idx;
510 d.points = &points;
511 d.x_shift = x_shift;
512 d.y_shift = y_shift;
513 d.ppems = &ppems;
514 d.next = NULL;
516 s = deltas_show_line(font, &d);
517 if (s)
519 fprintf(stderr, "Delta exception %s ignored.\n", s);
520 sdsfree(s);
523 emit_newline = 1;
526 point_idx = number_set_get_next(&points_iter);
529 ppem = number_set_get_next(&ppems_iter);
532 deltas = deltas->next;
535 if (font->debug && emit_newline)
536 fprintf(stderr, "\n");
538 font->deltas_data_head = deltas_data_head;
539 font->deltas_data_cur = LLRB_MIN(deltas_data, deltas_data_head);
541 return TA_Err_Ok;
545 /* the next functions are intended to restrict the use of LLRB stuff */
546 /* related to delta exceptions to this file, */
547 /* providing a means to access the data sequentially */
549 void
550 TA_deltas_get_next(FONT* font)
552 Node* node = (Node*)font->deltas_data_cur;
555 if (!node)
556 return;
558 node = LLRB_NEXT(deltas_data, /* unused */, node);
560 font->deltas_data_cur = node;
564 const Delta*
565 TA_deltas_get_delta(FONT* font)
567 Node* node = (Node*)font->deltas_data_cur;
570 return node ? &node->delta : NULL;
573 /* end of tadeltas.c */