1 /*
2 * Copyright © 2006 Keith Packard
3 *
4 * Permission to use, copy, modify, distribute, and sell this software and its
5 * documentation for any purpose is hereby granted without fee, provided that
6 * the above copyright notice appear in all copies and that both that copyright
7 * notice and this permission notice appear in supporting documentation, and
8 * that the name of the copyright holders not be used in advertising or
9 * publicity pertaining to distribution of the software without specific,
10 * written prior permission. The copyright holders make no representations
11 * about the suitability of this software for any purpose. It is provided "as
12 * is" without express or implied warranty.
13 *
14 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
16 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
19 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
20 * OF THIS SOFTWARE.
21 */
22
23 #include "fcint.h"
24
25 intptr_t
26 FcAlignSize (intptr_t size)
27 {
28 intptr_t rem = size % sizeof (FcAlign);
29 if (rem)
30 size += sizeof (FcAlign) - rem;
31 return size;
32 }
33
34 /*
35 * Serialization helper object -- allocate space in the
36 * yet-to-be-created linear array for a serialized font set
37 */
38
39 FcSerialize *
40 FcSerializeCreate (void)
41 {
42 FcSerialize *serialize;
43
44 serialize = malloc (sizeof (FcSerialize));
45 if (!serialize)
46 return NULL;
47 serialize->size = 0;
48 serialize->linear = NULL;
49 serialize->cs_freezer = NULL;
50 serialize->buckets = NULL;
51 serialize->buckets_count = 0;
52 serialize->buckets_used = 0;
53 serialize->buckets_used_max = 0;
54 return serialize;
55 }
56
57 void
58 FcSerializeDestroy (FcSerialize *serialize)
59 {
60 free (serialize->buckets);
61 if (serialize->cs_freezer)
62 FcCharSetFreezerDestroy (serialize->cs_freezer);
63 free (serialize);
64 }
65
66 static size_t
67 FcSerializeNextBucketIndex (const FcSerialize *serialize, size_t index)
68 {
69 if (index == 0)
70 index = serialize->buckets_count;
71 --index;
72 return index;
73 }
74
75 #if ((SIZEOF_VOID_P) * (CHAR_BIT)) == 32
76
77 /*
78 * Based on triple32
79 * https://github.com/skeeto/hash-prospector
80 */
81 static uintptr_t
82 FcSerializeHashPtr (const void *object)
83 {
84 uintptr_t x = (uintptr_t)object;
85 x ^= x >> 17;
86 x *= 0xed5ad4bbU;
87 x ^= x >> 11;
88 x *= 0xac4c1b51U;
89 x ^= x >> 15;
90 x *= 0x31848babU;
91 x ^= x >> 14;
92 return x ? x : 1; /* 0 reserved to mark empty, x starts out 0 */
93 }
94
95
96 #elif ((SIZEOF_VOID_P) * (CHAR_BIT)) == 64
97
98 /*
99 * Based on splittable64/splitmix64 from Mix13
100 * https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
101 * https://prng.di.unimi.it/splitmix64.c
102 */
103 static uintptr_t
104 FcSerializeHashPtr (const void *object)
105 {
106 uintptr_t x = (uintptr_t)object;
107 x ^= x >> 30;
108 x *= 0xbf58476d1ce4e5b9U;
109 x ^= x >> 27;
110 x *= 0x94d049bb133111ebU;
111 x ^= x >> 31;
112 return x ? x : 1; /* 0 reserved to mark empty, x starts out 0 */
113 }
114
115 #endif
116
117 static FcSerializeBucket*
118 FcSerializeFind (const FcSerialize *serialize, const void *object)
119 {
120 uintptr_t hash = FcSerializeHashPtr (object);
121 size_t buckets_count = serialize->buckets_count;
122 size_t index = hash & (buckets_count-1);
123 for (size_t n = 0; n < buckets_count; ++n) {
124 FcSerializeBucket* bucket = &serialize->buckets[index];
125 if (bucket->hash == 0) {
126 return NULL;
127 }
128 if (object == bucket->object) {
129 return bucket;
130 }
131 index = FcSerializeNextBucketIndex (serialize, index);
132 }
133 return NULL;
134 }
135
136 static FcSerializeBucket*
137 FcSerializeUncheckedSet (FcSerialize *serialize, FcSerializeBucket* insert) {
138 const void *object = insert->object;
139 size_t buckets_count = serialize->buckets_count;
140 size_t index = insert->hash & (buckets_count-1);
141 for (size_t n = 0; n < buckets_count; ++n) {
142 FcSerializeBucket* bucket = &serialize->buckets[index];
143 if (bucket->hash == 0) {
144 *bucket = *insert;
145 ++serialize->buckets_used;
146 return bucket;
147 }
148 if (object == bucket->object) {
149 /* FcSerializeAlloc should not allow this to happen. */
150 assert (0);
151 *bucket = *insert;
152 return bucket;
153 }
154 index = FcSerializeNextBucketIndex (serialize, index);
155 }
156 assert (0);
157 return NULL;
158 }
159
160 static FcBool
161 FcSerializeResize (FcSerialize *serialize, size_t new_count)
162 {
163 size_t old_used = serialize->buckets_used;
164 size_t old_count = serialize->buckets_count;
165 FcSerializeBucket *old_buckets = serialize->buckets;
166 FcSerializeBucket *old_buckets_end = old_buckets + old_count;
167
168 FcSerializeBucket *new_buckets = malloc (new_count * sizeof (*old_buckets));
169 if (!new_buckets)
170 return FcFalse;
171 FcSerializeBucket *new_buckets_end = new_buckets + new_count;
172 for (FcSerializeBucket *b = new_buckets; b < new_buckets_end; ++b)
173 b->hash = 0;
174
175 serialize->buckets = new_buckets;
176 serialize->buckets_count = new_count;
177 serialize->buckets_used = 0;
178 for (FcSerializeBucket *b = old_buckets; b < old_buckets_end; ++b)
179 if (b->hash != 0 && !FcSerializeUncheckedSet (serialize, b))
180 {
181 serialize->buckets = old_buckets;
182 serialize->buckets_count = old_count;
183 serialize->buckets_used = old_used;
184 free (new_buckets);
185 return FcFalse;
186 }
187 free (old_buckets);
188 return FcTrue;
189 }
190
191 static FcSerializeBucket*
192 FcSerializeSet (FcSerialize *serialize, const void *object, intptr_t offset)
193 {
194 if (serialize->buckets_used >= serialize->buckets_used_max)
195 {
196 size_t capacity = serialize->buckets_count;
197 if (capacity == 0)
198 capacity = 4;
199 else if (capacity > SIZE_MAX / 2u)
200 return NULL;
201 else
202 capacity *= 2;
203
204 if (!FcSerializeResize (serialize, capacity))
205 return NULL;
206
207 serialize->buckets_used_max = capacity / 4u * 3u;
208 }
209
210 FcSerializeBucket bucket;
211 bucket.object = object;
212 bucket.offset = offset;
213 bucket.hash = FcSerializeHashPtr (object);
214 return FcSerializeUncheckedSet (serialize, &bucket);
215 }
216
217 /*
218 * Allocate space for an object in the serialized array. Keep track
219 * of where the object is placed and only allocate one copy of each object
220 */
221 FcBool
222 FcSerializeAlloc (FcSerialize *serialize, const void *object, int size)
223 {
224 FcSerializeBucket *bucket = FcSerializeFind (serialize, object);
225 if (bucket)
226 return FcTrue;
227
228 if (!FcSerializeSet (serialize, object, serialize->size))
229 return FcFalse;
230
231 serialize->size += FcAlignSize (size);
232 return FcTrue;
233 }
234
235 /*
236 * Reserve space in the serialization array
237 */
238 intptr_t
239 FcSerializeReserve (FcSerialize *serialize, int size)
240 {
241 intptr_t offset = serialize->size;
242 serialize->size += FcAlignSize (size);
243 return offset;
244 }
245
246 /*
247 * Given an object, return the offset in the serialized array where
248 * the serialized copy of the object is stored
249 */
250 intptr_t
251 FcSerializeOffset (FcSerialize *serialize, const void *object)
252 {
253 FcSerializeBucket *bucket = FcSerializeFind (serialize, object);
254 return bucket ? bucket->offset : 0;
255 }
256
257 /*
258 * Given a cache and an object, return a pointer to where
259 * the serialized copy of the object is stored
260 */
261 void *
262 FcSerializePtr (FcSerialize *serialize, const void *object)
263 {
264 intptr_t offset = FcSerializeOffset (serialize, object);
265
266 if (!offset)
267 return NULL;
268 return (void *) ((char *) serialize->linear + offset);
269 }
270
271 FcBool
272 FcStrSerializeAlloc (FcSerialize *serialize, const FcChar8 *str)
273 {
274 return FcSerializeAlloc (serialize, str, strlen ((const char *) str) + 1);
275 }
276
277 FcChar8 *
278 FcStrSerialize (FcSerialize *serialize, const FcChar8 *str)
279 {
280 FcChar8 *str_serialize = FcSerializePtr (serialize, str);
281 if (!str_serialize)
282 return NULL;
283 strcpy ((char *) str_serialize, (const char *) str);
284 return str_serialize;
285 }
286 #include "fcaliastail.h"
287 #undef __fcserialize__