hash.c File Reference

#include <stdint.h>
#include <stddef.h>
#include "config.h"
#include "hash.h"

Go to the source code of this file.

Macros
#define	HASH32_PRIME   (uint32_t)(16777619u) /* Special prime number */
	This implementation is an optimized variation of the FNV-1a hash algorithm.
#define	HASH32_PSTEP(hash_, pb_)
	Process one byte from pointer (pointer is incremented).
#define	HASH32_CSTEP(hash_, b_)
	Same as the above but second arg is the value, not pointer.
#define	HASH32_RETURN_IF_DONE   do { if (--len == 0) return hash; } while(0)

Functions
uint32_t	hash32 (uint32_t prev_hash, const uint8_t *data, size_t len)
	Compute FNV-1a hash over a byte buffer.
uint64_t	hash64 (uint64_t prev_crc, void const *buffer0, size_t buf_len)
	CRC-64/ECMA-182 algoritm.

Macro Definition Documentation

HASH32_CSTEP

#define HASH32_CSTEP	(		hash_,
			b_ )

Value:

  do { \
  (hash_) ^= (uint8_t)(b_); \
  (hash_) *= HASH32_PRIME; \
} while( 0 )

Same as the above but second arg is the value, not pointer.

Note

No pointer autoincrement

Definition at line 49 of file hash.c.

Referenced by hash32().

HASH32_PRIME

#define HASH32_PRIME   (uint32_t)(16777619u) /* Special prime number */

This implementation is an optimized variation of the FNV-1a hash algorithm.

This is NOT a strict reference implementation of FNV, but preserves byte-equivalence of FNV-1a while improving memory throughput.

const char *test_vector3 = "The_Prefix/The_Name.txt"; const uint32_t ref_value = 0x6f914293;

Definition at line 32 of file hash.c.

HASH32_PSTEP

#define HASH32_PSTEP	(		hash_,
			pb_ )

Value:

  do { \
  (hash_) ^= *(const uint8_t *)(pb_++); \
  (hash_) *= HASH32_PRIME; \
} while(0)

Process one byte from pointer (pointer is incremented).

Parameters

hash_	hash accumulator
pb_	pointer to byte pointer (will be incremented)

Definition at line 40 of file hash.c.

Referenced by hash32().

HASH32_RETURN_IF_DONE

#define HASH32_RETURN_IF_DONE   do { if (--len == 0) return hash; } while(0)

Definition at line 57 of file hash.c.

Referenced by hash32().

Function Documentation

hash32()

uint32_t hash32	(	uint32_t	prev_hash,
		uint8_t const *	data,
		size_t	len )

Compute FNV-1a hash over a byte buffer.

This function supports incremental hashing:

h = hash32(HASH32_IV, data1, len1);
h = hash32(h,        data2, len2);
h = hash32(h,        data3, len3);
....

Parameters

prev_hash	previous hash value (use HASH32_IV for fresh hash)
data	Input byte buffer
len	Length of input buffer

Returns

Updated 32-bit FNV-1a hash

This function supports incremental hashing:

h = hash32(HASH32_IV, data1, len1);
h = hash32(h,        data2, len2);
h = hash32(h,        data3, len3);
....

Parameters

prev_hash	initial hash state (use HASH32_IV for fresh hash)
data	Input byte buffer
len	Length of input buffer

Returns

Updated 32-bit FNV-1a hash

Definition at line 79 of file hash.c.

References HASH32_CSTEP, HASH32_PSTEP, and HASH32_RETURN_IF_DONE.

Referenced by inode_lookup(), and inode_populate().

hash64()

uint64_t hash64	(	uint64_t	prev_hash,
		void const *	data,
		size_t	len )

CRC-64/ECMA-182 algoritm.

Compute CRC64/ECMA182 hash over a byte buffer.

Used for data integrity verification This is the reference software implementation of 64bit CRC, no tables. It is slower than table version but it does not use extra ram and speed here is not an issue as this functions is usually called by tarfs_fsck() code

CRC-64/ECMA-182 algoritm.

This function supports incremental hashing:

h = hash64(HASH64_IV, data1, len1);
h = hash64(h,        data2, len2);
h = hash64(h,        data3, len3);
....

Parameters

prev_hash	initial hash state (use HASH32_IV for fresh hash)
data	Input byte buffer
len	Length of input buffer

Returns

Updated 64-bit CRC64 sum

Definition at line 163 of file hash.c.

Referenced by tar_baddata().