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 Side-by-Side 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

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

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

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 += buckets[i]->hash;
			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

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: buckets[i]->hash];
					     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

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 = keyFunctions.hash(key);
	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

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

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 = keyFunctions.hash(key);
	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

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.021s