cdb format: hash table slots

This is a multi-part message in MIME format.
--------------090208030301020206070508
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hello,

I've been looking recently at the cdb format and come across a 
discrepancy between the actual output of cdbmake and the output I 
expected. Hopefully somebody will be able to tell me where I have gone 
wrong.

If I create a small cdb file with cdbmake, using the records

+13,3:thomas.mangin->foo
+11,3:markcowgill->bar

so that the hashes of both keys are stored in the same hash table, I 
notice that this table is 4 slots long.

Parsing the cdb file, I can see that the four slots are

2417049413, pointer to record with key markcowgill,
empty slot
empty slot
8948549, pointer to record with key thomas.mangin

where the value preceeding each pointer is a stored hash of the 
respective key.

Taken from http://cr.yp.to/cdb/cdb.txt,

"""
A record is located as follows. Compute the hash value of the key in
the record. The hash value modulo 256 is the number of a hash table.
The hash value divided by 256, modulo the length of that table, is a
slot number. Probe that slot, the next higher slot, and so on, until
you find the record or run into an empty slot.
"""

Reading this paragraph, I expected to be able able to find the entry for 
'markcowgill' by seeking to the starting position of the hash table + 
(2*4) * n bytes, where n = (hash / 256) % 4.

In this particular case, (hash / 256) % 4 = (2417049413 / 256) % 4 = 3, 
meaning that I skip past the value I'm looking for (jumping straight to 
'thomas.mangin') and falsely report that the key does not exist.

I can still retrieve a key by hardcoding the slot position to 0 or even 
reading each record sequentially but this doesn't seem to be the best 
way to read quickly and I would appreciate it if somebody could put me 
ok the right track.

In case it helps, I have written a rough and ready python cdb 
implementation to check the data and rewrite it in a format that does 
what I expect. I'm not sure that the write function is correct but I ran 
it on a fairly large dataset and it gave me the results I wanted.

Setting self.broken on line 31 to False forces slot number = 0 when 
performing a hash lookup and is the only way I can parse data generated 
by cdbmake


David

--------------090208030301020206070508
Content-Type: text/x-python;
 name="cdb.py"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="cdb.py"

#
# Copyright 2008 Exa Networks
# This code is placed in the public domain
#

import struct


class HashSlot:
	def __init__(self, value, position, total):
		self.position = position
		self.value = value
		self.minposition = (self.value /256) % total

	def __cmp__(self, other):
		if self.minposition < other.minposition:
			return -1
		if self.minposition > other.minposition:
			return 1
		return 0

	def __str__(self):
		return ''.join(struct.unpack('ssssssss', struct.pack('<II', self.value, self.position)))

	def __repr__(self):
		return ' '.join((str(v) for v in (self.value, self.position, self.minposition)))




class cdb (dict):
	def __init__(self, filename):
		self.filename = filename
		self.fd = open(filename, 'r')
		self.debug = True
		self.broken = True


	def __cdbhash(self, key):
		h = 5381 # mmmmagic
		for c in key:
			h = ((h << 5) + h) ^ ord(c)
		h = h & 0xffffffff
		return h

	def __find_hash_offset(self):
		self.fd.seek(0)
		d = self.fd.read(4)
		if not d.__len__() == 4:
			raise DataError, 'The specified file is not a valid cdb file'

		d = struct.unpack('<I', struct.pack('ssss', *(b for b in d)))
		return d[0]

	def __read_record(self, pos):
		self.fd.seek(pos)
		kl = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]
		dl = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]
		key = self.fd.read(kl)
		data = self.fd.read(dl)
		return 8 + kl + dl, key, data

	def __getitem__(self, item):
		hash = self.__cdbhash(item)
		n = hash % 256

		self.fd.seek(8*n)
		hash_pos = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]
		hash_len = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]

		if hash_len == 0:
			raise KeyError, item

		self.debug = n == 69

		slot = (hash/256) % hash_len
		if self.broken:
			slot = 0

		if self.debug:
			print item, '\ttable number is', n, '\thash', hash, 'is at byte postion', hash_pos, '\tslot offset is +%s'% slot, 'with', hash_len, 'slots'

		hash_pos += 8*slot 


		for i in xrange(hash_len - slot):
			self.fd.seek(hash_pos + 8*i)
			stored = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]
			pos = struct.unpack('<I', struct.pack('ssss', *(b for b in self.fd.read(4))))[0]


			if pos == 0:		# from http://cr.yp.to/cdb/cdb.txt
				if self.debug:
					print "FOUND\tPADDING"
				continue	# "If the byte position is 0, the slot is empty."

			if True or stored == hash:
				len, key, value = self.__read_record(pos)
				if self.debug:
					print "FOUND\t", key
				if key == item:
					if self.debug:
						print
						print
					return value


		raise KeyError, item


	def iteritems(self):
		end = self.__find_hash_offset() - 2048
		read = 0

		while read < end:
			len, key, value = self.__read_record(2048+read)
			read += len
			yield key, value

	def items(self):
		return [item for item in self.iteritems()]

	def iterkeys(self):
		return (key for key, value in self.iteritems())

	def keys(self):
		return [key for key, value in self.iteritems()]

	def itervalues(self):
		return (value for key, value in self.iteritems())

	def values(self):
		return [value for key, value in self.iteritems()]


	def write(self):
		wfd = open(self.filename+'.tmp', 'w')
		tables = {}
		for i in xrange(256):
			tables[i] = []

		wfd.seek(2048)
		written = 0
		for key, value in self.iteritems():
			pos = wfd.tell()
			kl = key.__len__()
			vl = value.__len__()
			key_len = ''.join(struct.unpack('ssss', struct.pack('<I', kl)))
			value_len = ''.join(struct.unpack('ssss', struct.pack('<I', vl)))

			wfd.write(key_len + value_len)
			wfd.write(key)
			wfd.write(value)

			written += kl + vl + 8

			hash = self.__cdbhash(key)
			n = hash % 256

			tables[n].append((hash, pos))




		for i in xrange(256):
			table = tables[i]
			count = len(table)


			hashtable = [HashSlot(hash, pos, count) for hash, pos in table]
			hashtable.sort()

			added = 0
			while True:
				hashtable = [HashSlot(hash, pos, count) for hash, pos in table]
				hashtable.sort()

				ok = True
				for n in xrange(hashtable.__len__()):
					if hashtable[n].minposition > n+added:
						ok = False
						break
				if ok:
					break
				count += 1
				added += 1


			tables[i] = [wfd.tell(), count]

			written = 0
			for slot in hashtable:
				minpos = slot.minposition
				if minpos > written:
					for j in xrange(minpos - written):
						wfd.write('\0\0\0\0\0\0\0\0')
						written +=1
				wfd.write(str(slot))
				written += 1

			for j in xrange(count - written):
				wfd.write('\0\0\0\0\0\0\0\0')
					


		wfd.seek(0)
		for i in xrange(256):
			pos, count = tables[i]
			s = ''.join(struct.unpack('ssssssss', struct.pack('<II', pos, count)))
			wfd.write(s)

		wfd.close()



if __name__ == '__main__':
	filename = '/home/david/exapasswd.cdb.test'

	c = cdb(filename)
	for key in c.iterkeys():
		c[key]

	c.write()

	d = cdb(filename+'.tmp')
	for key in d.iterkeys():
		d[key]


	x = dict(c.items())
	y = dict(d.items())
	print x == y

--------------090208030301020206070508--