ObjFW  Check-in [7cebeaa808]

Overview
Comment:OFMapTable: Rotate hashes randomly.

This makes the map table use the full range of the hash and not only the
least significant bits, making it harder for an attacker to find
collisions.

Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 7cebeaa808742056eccccd00275380af5e12a784c7f1635f168640492c5a7ec0
User & Date: js on 2013-01-03 22:26:36
Other Links: manifest | tags
Context
2013-01-07
13:35
Improve API for UTF-16 strings. check-in: 02ca89285f user: js tags: trunk
2013-01-03
22:26
OFMapTable: Rotate hashes randomly. check-in: 7cebeaa808 user: js tags: trunk
21:20
Add OFSystemInfo.h to ObjFW.h. check-in: 4039281f74 user: js tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified src/OFMapTable.h from [dcccbffbc5] to [3754665273].

︙︙
45
46
47
48
49
50
51

52
53
54
55
56
57
58

 *	  and values should be retained, released, compared and hashed.
 */
@interface OFMapTable: OFObject <OFCopying, OFFastEnumeration>
{
	of_map_table_functions_t keyFunctions, valueFunctions;
	struct of_map_table_bucket **buckets;
	uint32_t minCapacity, capacity, count;

	unsigned long mutations;
}

/*!
 * @brief Creates a new OFMapTable with the specified key and value functions.
 *
 * @param keyFunctions A structure of functions for handling keys








>








45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

 *	  and values should be retained, released, compared and hashed.
 */
@interface OFMapTable: OFObject <OFCopying, OFFastEnumeration>
{
	of_map_table_functions_t keyFunctions, valueFunctions;
	struct of_map_table_bucket **buckets;
	uint32_t minCapacity, capacity, count;
	uint8_t rotate;
	unsigned long mutations;
}

/*!
 * @brief Creates a new OFMapTable with the specified key and value functions.
 *
 * @param keyFunctions A structure of functions for handling keys
︙︙

Modified src/OFMapTable.m from [1a1f8d234d] to [3a2a927b76].

︙︙
148
149
150
151
152
153
154









155
156
157
158
159
160
161


		minCapacity = capacity;

		buckets = [self allocMemoryWithSize: sizeof(*buckets)
					      count: capacity];

		memset(buckets, 0, capacity * sizeof(*buckets));









	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}








>
>
>
>
>
>
>
>
>








148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170


		minCapacity = capacity;

		buckets = [self allocMemoryWithSize: sizeof(*buckets)
					      count: capacity];

		memset(buckets, 0, capacity * sizeof(*buckets));

		if (of_hash_seed != 0)
#if defined(OF_HAVE_ARC4RANDOM)
			rotate = arc4random() & 31;
#elif defined(OF_HAVE_RANDOM)
			rotate = random() & 31;
#else
			rotate = rand() & 31;
#endif
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}
︙︙
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217


- (uint32_t)hash
{
	uint32_t i, hash = 0;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			hash += buckets[i]->hash;
			hash += valueFunctions.hash(buckets[i]->value);
		}
	}

	return hash;
}









|








212
213
214
215
216
217
218
219
220
221
222
223
224
225
226


- (uint32_t)hash
{
	uint32_t i, hash = 0;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			hash += OF_ROR(buckets[i]->hash, rotate);
			hash += valueFunctions.hash(buckets[i]->value);
		}
	}

	return hash;
}
︙︙
225
226
227
228
229
230
231
232

233
234
235
236
237
238
239

	@try {
		uint32_t i;

		for (i = 0; i < capacity; i++)
			if (buckets[i] != NULL && buckets[i] != &deleted)
				[copy OF_setValue: buckets[i]->value
					   forKey: buckets[i]->key
					     hash: buckets[i]->hash];

	} @catch (id e) {
		[copy release];
		@throw e;
	}

	copy->minCapacity = MIN_CAPACITY;









|
>








234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249

	@try {
		uint32_t i;

		for (i = 0; i < capacity; i++)
			if (buckets[i] != NULL && buckets[i] != &deleted)
				[copy OF_setValue: buckets[i]->value
					   forKey: buckets[i]->key
					     hash: OF_ROR(buckets[i]->hash,
						       rotate)];
	} @catch (id e) {
		[copy release];
		@throw e;
	}

	copy->minCapacity = MIN_CAPACITY;
︙︙
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))








|








260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = OF_ROL(keyFunctions.hash(key), rotate);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))
︙︙
345
346
347
348
349
350
351

352
353
354
355
356
357
358

	void *old;

	if (key == NULL || value == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];


	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))








>








355
356
357
358
359
360
361
362
363
364
365
366
367
368
369

	void *old;

	if (key == NULL || value == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = OF_ROL(hash, rotate);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key))
︙︙
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454

	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key)) {








|








451
452
453
454
455
456
457
458
459
460
461
462
463
464
465

	uint32_t i, hash, last;

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = OF_ROL(keyFunctions.hash(key), rotate);
	last = capacity;

	for (i = hash & (capacity - 1); i < last && buckets[i] != NULL; i++) {
		if (buckets[i] == &deleted)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key)) {
︙︙

Modified src/macros.h from [60645bf692] to [19f9d4c0fa].

︙︙
324
325
326
327
328
329
330



331
332
333
334
335
336
337

#if defined(__MACH__) && defined(__arm__)
# define OF_IOS
#endif

#define OF_ROL(value, bits)						\
	(((value) << ((bits) % (sizeof(value) * 8))) |			\
	(value) >> (sizeof(value) * 8 - ((bits) % (sizeof(value) * 8))))




#define OF_HASH_INIT(hash) hash = of_hash_seed
#define OF_HASH_ADD(hash, byte)			\
	{					\
		hash += (uint8_t)(byte);	\
		hash += (hash << 10);		\
		hash ^= (hash >> 6);		\








>
>
>








324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340

#if defined(__MACH__) && defined(__arm__)
# define OF_IOS
#endif

#define OF_ROL(value, bits)						\
	(((value) << ((bits) % (sizeof(value) * 8))) |			\
	(value) >> (sizeof(value) * 8 - ((bits) % (sizeof(value) * 8))))
#define OF_ROR(value, bits)						\
	(((value) >> ((bits) % (sizeof(value) * 8))) |			\
	(value) << (sizeof(value) * 8 - ((bits) % (sizeof(value) * 8))))

#define OF_HASH_INIT(hash) hash = of_hash_seed
#define OF_HASH_ADD(hash, byte)			\
	{					\
		hash += (uint8_t)(byte);	\
		hash += (hash << 10);		\
		hash ^= (hash >> 6);		\
︙︙

Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.019s