serde_avro_fast 1.0.1

/// Implementation of the Rabin fingerprint algorithm using the Digest trait as described in [schema_fingerprints](https://avro.apache.org/docs/current/specification/#schema_fingerprints).
///
/// The digest is returned as the 8-byte little-endian encoding of the Rabin
/// hash. This is what is used for avro [single object encoding](https://avro.apache.org/docs/current/specification/#single-object-encoding)
pub struct Rabin {
	result: u64,
}

impl Default for Rabin {
	fn default() -> Self {
		Rabin { result: EMPTY64 }
	}
}

impl Rabin {
	pub(crate) fn write(&mut self, data: &[u8]) {
		for &b in data {
			self.result = (self.result >> 8) ^ FP_TABLE[((self.result ^ b as u64) & 0xFF) as usize];
		}
	}

	pub(crate) fn finish(self) -> [u8; 8] {
		self.result.to_le_bytes()
	}
}

impl std::fmt::Write for Rabin {
	fn write_str(&mut self, s: &str) -> std::fmt::Result {
		self.write(s.as_bytes());
		Ok(())
	}
}

const EMPTY64: u64 = 0xC15D213A_A4D7A795;

#[cfg(test)]
mod tests {
	use {super::Rabin, pretty_assertions::assert_eq};

	#[test]
	fn test() {
		let data: &[(&str, i64)] = &[
			(r#""null""#, 7195948357588979594),
			(r#""boolean""#, -6970731678124411036),
			(
				r#"{"name":"foo","type":"fixed","size":15}"#,
				1756455273707447556,
			),
			(
				r#"{"name":"PigValue","type":"record","fields":[{"name":"value","type":["null","int","long","PigValue"]}]}"#,
				-1759257747318642341,
			),
			("hello world", 2906301498937520992),
		];

		for (s, fp) in data {
			let mut hasher = Rabin::default();
			hasher.write(s.as_bytes());
			let result = i64::from_le_bytes(hasher.finish());
			assert_eq!(*fp, result);
		}
	}

	#[test]
	fn fp_table() {
		let mut fp_table: [u64; 256] = [0; 256];
		for i in 0..256 {
			let mut fp = i;
			for _ in 0..8 {
				fp = (fp >> 1)
					^ (super::EMPTY64 & u64::from_ne_bytes((-((fp & 1) as i64)).to_ne_bytes()));
			}
			fp_table[i as usize] = fp as u64;
			println!("\t{:#018X},", fp);
		}
		assert!(super::FP_TABLE as &[_] == &fp_table as &[_]);
	}
}

impl std::fmt::Debug for Rabin {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		f.debug_struct("Rabin")
			.field("result", &format_args!("{:#018X}", self.result))
			.finish()
	}
}

const FP_TABLE: &[u64; 256] = &[
	0x0000000000000000,
	0x2CF1CBA6B75351FA,
	0x59E3974D6EA6A3F4,
	0x75125CEBD9F5F20E,
	0xB3C72E9ADD4D47E8,
	0x9F36E53C6A1E1612,
	0xEA24B9D7B3EBE41C,
	0xC6D5727104B8B5E6,
	0xE5341F40F335C0FB,
	0xC9C5D4E644669101,
	0xBCD7880D9D93630F,
	0x902643AB2AC032F5,
	0x56F331DA2E788713,
	0x7A02FA7C992BD6E9,
	0x0F10A69740DE24E7,
	0x23E16D31F78D751D,
	0x48D27CF4AFC4CEDD,
	0x6423B75218979F27,
	0x1131EBB9C1626D29,
	0x3DC0201F76313CD3,
	0xFB15526E72898935,
	0xD7E499C8C5DAD8CF,
	0xA2F6C5231C2F2AC1,
	0x8E070E85AB7C7B3B,
	0xADE663B45CF10E26,
	0x8117A812EBA25FDC,
	0xF405F4F93257ADD2,
	0xD8F43F5F8504FC28,
	0x1E214D2E81BC49CE,
	0x32D0868836EF1834,
	0x47C2DA63EF1AEA3A,
	0x6B3311C55849BBC0,
	0x91A4F9E95F899DBA,
	0xBD55324FE8DACC40,
	0xC8476EA4312F3E4E,
	0xE4B6A502867C6FB4,
	0x2263D77382C4DA52,
	0x0E921CD535978BA8,
	0x7B80403EEC6279A6,
	0x57718B985B31285C,
	0x7490E6A9ACBC5D41,
	0x58612D0F1BEF0CBB,
	0x2D7371E4C21AFEB5,
	0x0182BA427549AF4F,
	0xC757C83371F11AA9,
	0xEBA60395C6A24B53,
	0x9EB45F7E1F57B95D,
	0xB24594D8A804E8A7,
	0xD976851DF04D5367,
	0xF5874EBB471E029D,
	0x809512509EEBF093,
	0xAC64D9F629B8A169,
	0x6AB1AB872D00148F,
	0x464060219A534575,
	0x33523CCA43A6B77B,
	0x1FA3F76CF4F5E681,
	0x3C429A5D0378939C,
	0x10B351FBB42BC266,
	0x65A10D106DDE3068,
	0x4950C6B6DA8D6192,
	0x8F85B4C7DE35D474,
	0xA3747F616966858E,
	0xD666238AB0937780,
	0xFA97E82C07C0267A,
	0xA1F3B1A7F6BC745F,
	0x8D027A0141EF25A5,
	0xF81026EA981AD7AB,
	0xD4E1ED4C2F498651,
	0x12349F3D2BF133B7,
	0x3EC5549B9CA2624D,
	0x4BD7087045579043,
	0x6726C3D6F204C1B9,
	0x44C7AEE70589B4A4,
	0x68366541B2DAE55E,
	0x1D2439AA6B2F1750,
	0x31D5F20CDC7C46AA,
	0xF700807DD8C4F34C,
	0xDBF14BDB6F97A2B6,
	0xAEE31730B66250B8,
	0x8212DC9601310142,
	0xE921CD535978BA82,
	0xC5D006F5EE2BEB78,
	0xB0C25A1E37DE1976,
	0x9C3391B8808D488C,
	0x5AE6E3C98435FD6A,
	0x7617286F3366AC90,
	0x03057484EA935E9E,
	0x2FF4BF225DC00F64,
	0x0C15D213AA4D7A79,
	0x20E419B51D1E2B83,
	0x55F6455EC4EBD98D,
	0x79078EF873B88877,
	0xBFD2FC8977003D91,
	0x9323372FC0536C6B,
	0xE6316BC419A69E65,
	0xCAC0A062AEF5CF9F,
	0x3057484EA935E9E5,
	0x1CA683E81E66B81F,
	0x69B4DF03C7934A11,
	0x454514A570C01BEB,
	0x839066D47478AE0D,
	0xAF61AD72C32BFFF7,
	0xDA73F1991ADE0DF9,
	0xF6823A3FAD8D5C03,
	0xD563570E5A00291E,
	0xF9929CA8ED5378E4,
	0x8C80C04334A68AEA,
	0xA0710BE583F5DB10,
	0x66A47994874D6EF6,
	0x4A55B232301E3F0C,
	0x3F47EED9E9EBCD02,
	0x13B6257F5EB89CF8,
	0x788534BA06F12738,
	0x5474FF1CB1A276C2,
	0x2166A3F7685784CC,
	0x0D976851DF04D536,
	0xCB421A20DBBC60D0,
	0xE7B3D1866CEF312A,
	0x92A18D6DB51AC324,
	0xBE5046CB024992DE,
	0x9DB12BFAF5C4E7C3,
	0xB140E05C4297B639,
	0xC452BCB79B624437,
	0xE8A377112C3115CD,
	0x2E7605602889A02B,
	0x0287CEC69FDAF1D1,
	0x7795922D462F03DF,
	0x5B64598BF17C5225,
	0xC15D213AA4D7A795,
	0xEDACEA9C1384F66F,
	0x98BEB677CA710461,
	0xB44F7DD17D22559B,
	0x729A0FA0799AE07D,
	0x5E6BC406CEC9B187,
	0x2B7998ED173C4389,
	0x0788534BA06F1273,
	0x24693E7A57E2676E,
	0x0898F5DCE0B13694,
	0x7D8AA9373944C49A,
	0x517B62918E179560,
	0x97AE10E08AAF2086,
	0xBB5FDB463DFC717C,
	0xCE4D87ADE4098372,
	0xE2BC4C0B535AD288,
	0x898F5DCE0B136948,
	0xA57E9668BC4038B2,
	0xD06CCA8365B5CABC,
	0xFC9D0125D2E69B46,
	0x3A487354D65E2EA0,
	0x16B9B8F2610D7F5A,
	0x63ABE419B8F88D54,
	0x4F5A2FBF0FABDCAE,
	0x6CBB428EF826A9B3,
	0x404A89284F75F849,
	0x3558D5C396800A47,
	0x19A91E6521D35BBD,
	0xDF7C6C14256BEE5B,
	0xF38DA7B29238BFA1,
	0x869FFB594BCD4DAF,
	0xAA6E30FFFC9E1C55,
	0x50F9D8D3FB5E3A2F,
	0x7C0813754C0D6BD5,
	0x091A4F9E95F899DB,
	0x25EB843822ABC821,
	0xE33EF64926137DC7,
	0xCFCF3DEF91402C3D,
	0xBADD610448B5DE33,
	0x962CAAA2FFE68FC9,
	0xB5CDC793086BFAD4,
	0x993C0C35BF38AB2E,
	0xEC2E50DE66CD5920,
	0xC0DF9B78D19E08DA,
	0x060AE909D526BD3C,
	0x2AFB22AF6275ECC6,
	0x5FE97E44BB801EC8,
	0x7318B5E20CD34F32,
	0x182BA427549AF4F2,
	0x34DA6F81E3C9A508,
	0x41C8336A3A3C5706,
	0x6D39F8CC8D6F06FC,
	0xABEC8ABD89D7B31A,
	0x871D411B3E84E2E0,
	0xF20F1DF0E77110EE,
	0xDEFED65650224114,
	0xFD1FBB67A7AF3409,
	0xD1EE70C110FC65F3,
	0xA4FC2C2AC90997FD,
	0x880DE78C7E5AC607,
	0x4ED895FD7AE273E1,
	0x62295E5BCDB1221B,
	0x173B02B01444D015,
	0x3BCAC916A31781EF,
	0x60AE909D526BD3CA,
	0x4C5F5B3BE5388230,
	0x394D07D03CCD703E,
	0x15BCCC768B9E21C4,
	0xD369BE078F269422,
	0xFF9875A13875C5D8,
	0x8A8A294AE18037D6,
	0xA67BE2EC56D3662C,
	0x859A8FDDA15E1331,
	0xA96B447B160D42CB,
	0xDC791890CFF8B0C5,
	0xF088D33678ABE13F,
	0x365DA1477C1354D9,
	0x1AAC6AE1CB400523,
	0x6FBE360A12B5F72D,
	0x434FFDACA5E6A6D7,
	0x287CEC69FDAF1D17,
	0x048D27CF4AFC4CED,
	0x719F7B249309BEE3,
	0x5D6EB082245AEF19,
	0x9BBBC2F320E25AFF,
	0xB74A095597B10B05,
	0xC25855BE4E44F90B,
	0xEEA99E18F917A8F1,
	0xCD48F3290E9ADDEC,
	0xE1B9388FB9C98C16,
	0x94AB6464603C7E18,
	0xB85AAFC2D76F2FE2,
	0x7E8FDDB3D3D79A04,
	0x527E16156484CBFE,
	0x276C4AFEBD7139F0,
	0x0B9D81580A22680A,
	0xF10A69740DE24E70,
	0xDDFBA2D2BAB11F8A,
	0xA8E9FE396344ED84,
	0x8418359FD417BC7E,
	0x42CD47EED0AF0998,
	0x6E3C8C4867FC5862,
	0x1B2ED0A3BE09AA6C,
	0x37DF1B05095AFB96,
	0x143E7634FED78E8B,
	0x38CFBD924984DF71,
	0x4DDDE17990712D7F,
	0x612C2ADF27227C85,
	0xA7F958AE239AC963,
	0x8B08930894C99899,
	0xFE1ACFE34D3C6A97,
	0xD2EB0445FA6F3B6D,
	0xB9D81580A22680AD,
	0x9529DE261575D157,
	0xE03B82CDCC802359,
	0xCCCA496B7BD372A3,
	0x0A1F3B1A7F6BC745,
	0x26EEF0BCC83896BF,
	0x53FCAC5711CD64B1,
	0x7F0D67F1A69E354B,
	0x5CEC0AC051134056,
	0x701DC166E64011AC,
	0x050F9D8D3FB5E3A2,
	0x29FE562B88E6B258,
	0xEF2B245A8C5E07BE,
	0xC3DAEFFC3B0D5644,
	0xB6C8B317E2F8A44A,
	0x9A3978B155ABF5B0,
];