Debian Codegraph @

src/alg/blitsort.c

raw
1 /*
2 * blitsort.c - sorting blits in an image
3 */
4
5 /* The algorithm is taken from DjVuLibre with minor (stupid) changes. */
6
7
8 #include "../base/mdjvucfg.h"
9 #include <minidjvu/minidjvu.h>
10 #include <stdlib.h>
11
12
13
14 typedef struct
15 {
16 int32 left, top, right, bottom;
17 int32 original_index;
18 } BlitPassport;
19
20
21 static int compare_top_edges_downward(const void *p1, const void *p2)
22 {
23 const BlitPassport *bp1 = (const BlitPassport *) p1;
24 const BlitPassport *bp2 = (const BlitPassport *) p2;
25 int32 d;
26 d = bp1->top - bp2->top;
27 if (d) return d;
28 d = bp1->left - bp2->left;
29 if (d) return d;
30 return 0;
31 }
32
33 static int compare_left_edges_rightward(const void *p1, const void *p2)
34 {
35 const BlitPassport *bp1 = (const BlitPassport *) p1;
36 const BlitPassport *bp2 = (const BlitPassport *) p2;
37 int32 d;
38 d = bp1->left - bp2->left;
39 if (d) return d;
40 d = bp1->top - bp2->top;
41 if (d) return d;
42 return 0;
43 }
44
45 static int compare_integers_reversed(const void *p1, const void *p2)
46 {
47 if (sizeof(int) == sizeof(int32)) /* hopefully compilers will optimize it */
48 {
49 return * (const int *) p2 - * (const int *) p1;
50 }
51 else
52 {
53 int32 d = * (const int32 *) p2 - * (const int32 *) p1;
54 return d > 0 ? 1 :
55 d < 0 ? -1 : 0;
56 }
57 }
58
59
60 MDJVU_IMPLEMENT void mdjvu_sort_blits(mdjvu_image_t img)
61 {
62 /* We're going to sort only blits with `is_a_letter' flag set. */
63
64 int32 char_blit_count = 0;
65 int32 blit_count, i, j, maxtopchange, ccno;
66 BlitPassport *bps;
67 int32 *bottoms, *passport_of_blit;
68
69 if (!mdjvu_image_has_not_a_letter_flags(img))
70 mdjvu_calculate_not_a_letter_flags(img);
71
72 /* Count letter blits */
73 blit_count = mdjvu_image_get_blit_count(img);
74 for (i = 0; i < blit_count; i++)
75 {
76 mdjvu_bitmap_t bmp = mdjvu_image_get_blit_bitmap(img, i);
77 if (!mdjvu_image_get_not_a_letter_flag(img, bmp))
78 char_blit_count++;
79 }
80
81 if (char_blit_count < 2) return;
82
83 /* Allocate `bps' and `bottoms' arrays */
84 bps = (BlitPassport *) malloc(char_blit_count * sizeof(BlitPassport));
85 bottoms = (int32 *) malloc(char_blit_count * sizeof(int32));
86
87 /* Fill in `bps' with character blit passports */
88 j = 0;
89 for (i = 0; i < blit_count; i++)
90 {
91 mdjvu_bitmap_t bmp = mdjvu_image_get_blit_bitmap(img, i);
92 if (!mdjvu_image_get_not_a_letter_flag(img, bmp))
93 {
94 int32 x = bps[j].left = mdjvu_image_get_blit_x(img, i);
95 int32 y = bps[j].top = mdjvu_image_get_blit_y(img, i);;
96 bps[j].right = x + mdjvu_bitmap_get_width(bmp) - 1;
97 bps[j].bottom = y + mdjvu_bitmap_get_height(bmp) - 1;
98 bps[j].original_index = i;
99 j++;
100 }
101 }
102
103 /* Sort the BlitPassports list in top-to-bottom order. */
104 qsort(bps, char_blit_count, sizeof(BlitPassport),
105 &compare_top_edges_downward);
106
107 /* Subdivide the ccarray list roughly into text lines [LYB] */
108 /* Determine maximal top deviation */
109 maxtopchange = mdjvu_image_get_width(img) / 40;
110 if (maxtopchange < 32) maxtopchange = 32;
111
112 /* Loop until processing all ccs */
113 ccno = 0;
114 while (ccno < char_blit_count) /* ccno will be increasing constantly */
115 {
116 /* Gather first line approximation */
117 int32 sublist_top = bps[ccno].top;
118 int32 sublist_bottom = bps[ccno].bottom;
119
120 int32 nccno;
121
122 /* nccno will be at least ccno + 1,
123 * or otherwise we're hung.
124 */
125 for (nccno = ccno; nccno < char_blit_count; nccno++)
126 {
127 int32 bottom;
128 if (bps[nccno].top > sublist_bottom) break;
129 if (bps[nccno].top > sublist_top + maxtopchange) break;
130 bottom = bps[nccno].bottom;
131 bottoms[nccno - ccno] = bottom;
132 if (bottom > sublist_bottom)
133 sublist_bottom = bottom;
134 }
135
136 /* If more than one candidate cc for the line */
137 if (nccno > ccno + 1)
138 {
139 /* Compute median bottom */
140 int32 bottom;
141 qsort(bottoms, nccno - ccno, sizeof(int32),
142 &compare_integers_reversed);
143 bottom = bottoms[ (nccno - ccno - 1) / 2 ];
144
145 /* Compose final line */
146 for (nccno = ccno; nccno < char_blit_count; nccno++)
147 if (bps[nccno].top > bottom)
148 break;
149
150 /* Sort final line */
151 qsort(bps + ccno, nccno - ccno, sizeof(BlitPassport),
152 &compare_left_edges_rightward);
153 }
154
155 /* Next line */
156 ccno = nccno;
157 }
158
159 /* Permute the blits according to `bps' */
160 passport_of_blit = (int32 *) malloc(blit_count * sizeof(int32));
161 for (i = 0; i < blit_count; i++)
162 passport_of_blit[i] = -1;
163 for (i = 0; i < char_blit_count; i++)
164 passport_of_blit[bps[i].original_index] = i;
165
166 /* We'll maintain that bps[i].original_index points to the same blit */
167 for (i = 0; i < char_blit_count; i++)
168 {
169 int32 blit_to_put_here = bps[i].original_index;
170 mdjvu_image_exchange_blits(img, blit_to_put_here, i);
171 if (passport_of_blit[i] != -1)
172 bps[passport_of_blit[i]].original_index = blit_to_put_here;
173 passport_of_blit[blit_to_put_here] = passport_of_blit[i];
174 }
175
176 free(passport_of_blit);
177 free(bps);
178 free(bottoms);
179 }