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
25intptr_t
26FcAlignSize (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
39FcSerialize *
40FcSerializeCreate (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
57void
58FcSerializeDestroy (FcSerialize *serialize)
59{
60    free (serialize->buckets);
61    if (serialize->cs_freezer)
62	FcCharSetFreezerDestroy (serialize->cs_freezer);
63    free (serialize);
64}
65
66static size_t
67FcSerializeNextBucketIndex (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 */
81static uintptr_t
82FcSerializeHashPtr (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 */
103static uintptr_t
104FcSerializeHashPtr (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
117static FcSerializeBucket*
118FcSerializeFind (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
136static FcSerializeBucket*
137FcSerializeUncheckedSet (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
160static FcBool
161FcSerializeResize (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
191static FcSerializeBucket*
192FcSerializeSet (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 */
221FcBool
222FcSerializeAlloc (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 */
238intptr_t
239FcSerializeReserve (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 */
250intptr_t
251FcSerializeOffset (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 */
261void *
262FcSerializePtr (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
271FcBool
272FcStrSerializeAlloc (FcSerialize *serialize, const FcChar8 *str)
273{
274    return FcSerializeAlloc (serialize, str, strlen ((const char *) str) + 1);
275}
276
277FcChar8 *
278FcStrSerialize (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__
288