KenLM update: Bhiksha's trick, simple test for lms without unk, auto-detect binary files instead of requiring them to be specified at runtime.

4 files changed, 164 insertions, 132 deletions

diff --git a/klm/util/bit_packing.hh b/klm/util/bit_packing.hh
index b35d80c8..9f47d559 100644
--- a/klm/util/bit_packing.hh
+++ b/klm/util/bit_packing.hh
@@ -107,9 +107,20 @@ void BitPackingSanity();
 uint8_t RequiredBits(uint64_t max_value);
 
 struct BitsMask {
+  static BitsMask ByMax(uint64_t max_value) {
+    BitsMask ret;
+    ret.FromMax(max_value);
+    return ret;
+  }
+  static BitsMask ByBits(uint8_t bits) {
+    BitsMask ret;
+    ret.bits = bits;
+    ret.mask = (1ULL << bits) - 1;
+    return ret;
+  }
   void FromMax(uint64_t max_value) {
     bits = RequiredBits(max_value);
-    mask = (1 << bits) - 1;
+    mask = (1ULL << bits) - 1;
   }
   uint8_t bits;
   uint64_t mask;
diff --git a/klm/util/murmur_hash.cc b/klm/util/murmur_hash.cc
index d58a0727..fec47fd9 100644
--- a/klm/util/murmur_hash.cc
+++ b/klm/util/murmur_hash.cc
@@ -1,129 +1,129 @@
-/* Downloaded from http://sites.google.com/site/murmurhash/ which says "All

- * code is released to the public domain. For business purposes, Murmurhash is

- * under the MIT license."

- * This is modified from the original:

- * ULL tag on 0xc6a4a7935bd1e995 so this will compile on 32-bit.  

- * length changed to unsigned int.  

- * placed in namespace util

- * add MurmurHashNative

- * default option = 0 for seed

- */

-

-#include "util/murmur_hash.hh"

-

-namespace util {

-

-//-----------------------------------------------------------------------------

-// MurmurHash2, 64-bit versions, by Austin Appleby

-

-// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment 

-// and endian-ness issues if used across multiple platforms.

-

-// 64-bit hash for 64-bit platforms

-

-uint64_t MurmurHash64A ( const void * key, std::size_t len, unsigned int seed )

-{

-  const uint64_t m = 0xc6a4a7935bd1e995ULL;

-  const int r = 47;

-

-  uint64_t h = seed ^ (len * m);

-

-  const uint64_t * data = (const uint64_t *)key;

-  const uint64_t * end = data + (len/8);

-

-  while(data != end)

-  {

-    uint64_t k = *data++;

-

-    k *= m; 

-    k ^= k >> r; 

-    k *= m; 

-    

-    h ^= k;

-    h *= m; 

-  }

-

-  const unsigned char * data2 = (const unsigned char*)data;

-

-  switch(len & 7)

-  {

-  case 7: h ^= uint64_t(data2[6]) << 48;

-  case 6: h ^= uint64_t(data2[5]) << 40;

-  case 5: h ^= uint64_t(data2[4]) << 32;

-  case 4: h ^= uint64_t(data2[3]) << 24;

-  case 3: h ^= uint64_t(data2[2]) << 16;

-  case 2: h ^= uint64_t(data2[1]) << 8;

-  case 1: h ^= uint64_t(data2[0]);

-          h *= m;

-  };

- 

-  h ^= h >> r;

-  h *= m;

-  h ^= h >> r;

-

-  return h;

-} 

-

-

-// 64-bit hash for 32-bit platforms

-

-uint64_t MurmurHash64B ( const void * key, std::size_t len, unsigned int seed )

-{

-  const unsigned int m = 0x5bd1e995;

-  const int r = 24;

-

-  unsigned int h1 = seed ^ len;

-  unsigned int h2 = 0;

-

-  const unsigned int * data = (const unsigned int *)key;

-

-  while(len >= 8)

-  {

-    unsigned int k1 = *data++;

-    k1 *= m; k1 ^= k1 >> r; k1 *= m;

-    h1 *= m; h1 ^= k1;

-    len -= 4;

-

-    unsigned int k2 = *data++;

-    k2 *= m; k2 ^= k2 >> r; k2 *= m;

-    h2 *= m; h2 ^= k2;

-    len -= 4;

-  }

-

-  if(len >= 4)

-  {

-    unsigned int k1 = *data++;

-    k1 *= m; k1 ^= k1 >> r; k1 *= m;

-    h1 *= m; h1 ^= k1;

-    len -= 4;

-  }

-

-  switch(len)

-  {

-  case 3: h2 ^= ((unsigned char*)data)[2] << 16;

-  case 2: h2 ^= ((unsigned char*)data)[1] << 8;

-  case 1: h2 ^= ((unsigned char*)data)[0];

-      h2 *= m;

-  };

-

-  h1 ^= h2 >> 18; h1 *= m;

-  h2 ^= h1 >> 22; h2 *= m;

-  h1 ^= h2 >> 17; h1 *= m;

-  h2 ^= h1 >> 19; h2 *= m;

-

-  uint64_t h = h1;

-

-  h = (h << 32) | h2;

-

-  return h;

-}

-

-uint64_t MurmurHashNative(const void * key, std::size_t len, unsigned int seed) {

-  if (sizeof(int) == 4) {

-    return MurmurHash64B(key, len, seed);

-  } else {

-    return MurmurHash64A(key, len, seed);

-  }

-}

-

-} // namespace util

+/* Downloaded from http://sites.google.com/site/murmurhash/ which says "All
+ * code is released to the public domain. For business purposes, Murmurhash is
+ * under the MIT license."
+ * This is modified from the original:
+ * ULL tag on 0xc6a4a7935bd1e995 so this will compile on 32-bit.  
+ * length changed to unsigned int.  
+ * placed in namespace util
+ * add MurmurHashNative
+ * default option = 0 for seed
+ */
+
+#include "util/murmur_hash.hh"
+
+namespace util {
+
+//-----------------------------------------------------------------------------
+// MurmurHash2, 64-bit versions, by Austin Appleby
+
+// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment 
+// and endian-ness issues if used across multiple platforms.
+
+// 64-bit hash for 64-bit platforms
+
+uint64_t MurmurHash64A ( const void * key, std::size_t len, unsigned int seed )
+{
+  const uint64_t m = 0xc6a4a7935bd1e995ULL;
+  const int r = 47;
+
+  uint64_t h = seed ^ (len * m);
+
+  const uint64_t * data = (const uint64_t *)key;
+  const uint64_t * end = data + (len/8);
+
+  while(data != end)
+  {
+    uint64_t k = *data++;
+
+    k *= m; 
+    k ^= k >> r; 
+    k *= m; 
+    
+    h ^= k;
+    h *= m; 
+  }
+
+  const unsigned char * data2 = (const unsigned char*)data;
+
+  switch(len & 7)
+  {
+  case 7: h ^= uint64_t(data2[6]) << 48;
+  case 6: h ^= uint64_t(data2[5]) << 40;
+  case 5: h ^= uint64_t(data2[4]) << 32;
+  case 4: h ^= uint64_t(data2[3]) << 24;
+  case 3: h ^= uint64_t(data2[2]) << 16;
+  case 2: h ^= uint64_t(data2[1]) << 8;
+  case 1: h ^= uint64_t(data2[0]);
+          h *= m;
+  };
+ 
+  h ^= h >> r;
+  h *= m;
+  h ^= h >> r;
+
+  return h;
+} 
+
+
+// 64-bit hash for 32-bit platforms
+
+uint64_t MurmurHash64B ( const void * key, std::size_t len, unsigned int seed )
+{
+  const unsigned int m = 0x5bd1e995;
+  const int r = 24;
+
+  unsigned int h1 = seed ^ len;
+  unsigned int h2 = 0;
+
+  const unsigned int * data = (const unsigned int *)key;
+
+  while(len >= 8)
+  {
+    unsigned int k1 = *data++;
+    k1 *= m; k1 ^= k1 >> r; k1 *= m;
+    h1 *= m; h1 ^= k1;
+    len -= 4;
+
+    unsigned int k2 = *data++;
+    k2 *= m; k2 ^= k2 >> r; k2 *= m;
+    h2 *= m; h2 ^= k2;
+    len -= 4;
+  }
+
+  if(len >= 4)
+  {
+    unsigned int k1 = *data++;
+    k1 *= m; k1 ^= k1 >> r; k1 *= m;
+    h1 *= m; h1 ^= k1;
+    len -= 4;
+  }
+
+  switch(len)
+  {
+  case 3: h2 ^= ((unsigned char*)data)[2] << 16;
+  case 2: h2 ^= ((unsigned char*)data)[1] << 8;
+  case 1: h2 ^= ((unsigned char*)data)[0];
+      h2 *= m;
+  };
+
+  h1 ^= h2 >> 18; h1 *= m;
+  h2 ^= h1 >> 22; h2 *= m;
+  h1 ^= h2 >> 17; h1 *= m;
+  h2 ^= h1 >> 19; h2 *= m;
+
+  uint64_t h = h1;
+
+  h = (h << 32) | h2;
+
+  return h;
+}
+
+uint64_t MurmurHashNative(const void * key, std::size_t len, unsigned int seed) {
+  if (sizeof(int) == 4) {
+    return MurmurHash64B(key, len, seed);
+  } else {
+    return MurmurHash64A(key, len, seed);
+  }
+}
+
+} // namespace util
diff --git a/klm/util/probing_hash_table.hh b/klm/util/probing_hash_table.hh
index 00be0ed7..2ec342a6 100644
--- a/klm/util/probing_hash_table.hh
+++ b/klm/util/probing_hash_table.hh
@@ -57,7 +57,7 @@ template <class PackingT, class HashT, class EqualT = std::equal_to<typename Pac
         equal_(equal_func),
         entries_(0)
 #ifdef DEBUG
-        , initialized_(true),
+        , initialized_(true)
 #endif
     {}
 
diff --git a/klm/util/sorted_uniform.hh b/klm/util/sorted_uniform.hh
index 84d7aa02..0d6ecbbd 100644
--- a/klm/util/sorted_uniform.hh
+++ b/klm/util/sorted_uniform.hh
@@ -12,7 +12,7 @@ namespace util {
 template <class T> class IdentityAccessor {
   public:
     typedef T Key;
-    T operator()(const uint64_t *in) const { return *in; }
+    T operator()(const T *in) const { return *in; }
 };
 
 struct Pivot64 {
@@ -101,6 +101,27 @@ template <class Iterator, class Accessor, class Pivot> bool SortedUniformFind(co
   return BoundedSortedUniformFind<Iterator, Accessor, Pivot>(accessor, begin, below, end, above, key, out);
 }
 
+// May return begin - 1.
+template <class Iterator, class Accessor> Iterator BinaryBelow(
+    const Accessor &accessor,
+    Iterator begin,
+    Iterator end,
+    const typename Accessor::Key key) {
+  while (end > begin) {
+    Iterator pivot(begin + (end - begin) / 2);
+    typename Accessor::Key mid(accessor(pivot));
+    if (mid < key) {
+      begin = pivot + 1;
+    } else if (mid > key) {
+      end = pivot;
+    } else {
+      for (++pivot; (pivot < end) && accessor(pivot) == mid; ++pivot) {}
+      return pivot - 1;
+    }
+  }
+  return begin - 1;
+}
+
 // To use this template, you need to define a Pivot function to match Key.  
 template <class PackingT> class SortedUniformMap {
   public: