[base][coding] Burrows-Wheeler coder.

8 files changed, 97 insertions, 1 deletions

diff --git a/base/CMakeLists.txt b/base/CMakeLists.txt
index fe64857e8a..3db7f7afa9 100644
--- a/base/CMakeLists.txt
+++ b/base/CMakeLists.txt
@@ -36,6 +36,8 @@ set(
   math.hpp
   matrix.hpp
   mem_trie.hpp
+  move_to_front.cpp
+  move_to_front.hpp
   mutex.hpp
   newtype.hpp
   normalize_unicode.cpp
diff --git a/base/base.pro b/base/base.pro
index cb2cdd8888..64f3336cb0 100644
--- a/base/base.pro
+++ b/base/base.pro
@@ -18,6 +18,7 @@ SOURCES += \
     levenshtein_dfa.cpp \
     logging.cpp \
     lower_case.cpp \
+    move_to_front.cpp \
     normalize_unicode.cpp \
     pprof.cpp \
     random.cpp \
@@ -63,6 +64,7 @@ HEADERS += \
     math.hpp \
     matrix.hpp \
     mem_trie.hpp \
+    move_to_front.hpp \
     mutex.hpp \
     newtype.hpp \
     observer_list.hpp \
diff --git a/base/base_tests/CMakeLists.txt b/base/base_tests/CMakeLists.txt
index 277983f38d..ad29bf1f97 100644
--- a/base/base_tests/CMakeLists.txt
+++ b/base/base_tests/CMakeLists.txt
@@ -17,6 +17,7 @@ set(
   math_test.cpp
   matrix_test.cpp
   mem_trie_test.cpp
+  move_to_front_tests.cpp
   newtype_test.cpp
   observer_list_test.cpp
   range_iterator_test.cpp
diff --git a/base/base_tests/base_tests.pro b/base/base_tests/base_tests.pro
index 1f2025da66..501e9d1e3a 100644
--- a/base/base_tests/base_tests.pro
+++ b/base/base_tests/base_tests.pro
@@ -28,6 +28,7 @@ SOURCES += \
   math_test.cpp \
   matrix_test.cpp \
   mem_trie_test.cpp \
+  move_to_front_tests.cpp \
   observer_list_test.cpp \
   range_iterator_test.cpp \
   ref_counted_tests.cpp \
diff --git a/base/base_tests/move_to_front_tests.cpp b/base/base_tests/move_to_front_tests.cpp
new file mode 100644
index 0000000000..a18c9e7abf
--- /dev/null
+++ b/base/base_tests/move_to_front_tests.cpp
@@ -0,0 +1,32 @@
+#include "testing/testing.hpp"
+
+#include "base/move_to_front.hpp"
+
+#include <cstdint>
+
+using namespace base;
+
+namespace
+{
+UNIT_TEST(MoveToFront_Smoke)
+{
+  MoveToFront mtf;
+  for (size_t i = 0; i < 256; ++i)
+    TEST_EQUAL(mtf[i], i, ());
+
+  // Initially 3 should be on the 3-th position.
+  TEST_EQUAL(mtf.Transform(3), 3, ());
+
+  // After the first transform, 3 should be moved to the 0-th position.
+  TEST_EQUAL(mtf.Transform(3), 0, ());
+  TEST_EQUAL(mtf.Transform(3), 0, ());
+  TEST_EQUAL(mtf.Transform(3), 0, ());
+
+  TEST_EQUAL(mtf[0], 3, ());
+  TEST_EQUAL(mtf[1], 0, ());
+  TEST_EQUAL(mtf[2], 1, ());
+  TEST_EQUAL(mtf[3], 2, ());
+  for (size_t i = 4; i < 256; ++i)
+    TEST_EQUAL(mtf[i], i, ());
+}
+}  // namespace
diff --git a/base/move_to_front.cpp b/base/move_to_front.cpp
new file mode 100644
index 0000000000..6091c3f232
--- /dev/null
+++ b/base/move_to_front.cpp
@@ -0,0 +1,33 @@
+#include "base/move_to_front.hpp"
+
+#include "base/assert.hpp"
+
+#include <algorithm>
+#include <cstring>
+
+using namespace std;
+
+namespace base
+{
+// static
+size_t constexpr MoveToFront::kNumBytes;
+
+MoveToFront::MoveToFront()
+{
+  for (size_t i = 0; i < kNumBytes; ++i)
+    m_order[i] = i;
+}
+
+uint8_t MoveToFront::Transform(uint8_t b)
+{
+  auto const it = find(m_order.begin(), m_order.end(), b);
+  ASSERT(it != m_order.end(), ());
+
+  size_t const result = distance(m_order.begin(), it);
+  ASSERT_LESS(result, kNumBytes, ());
+
+  rotate(m_order.begin(), it, it + 1);
+  ASSERT_EQUAL(m_order[0], b, ());
+  return static_cast<uint8_t>(result);
+}
+}  // namespace base
diff --git a/base/move_to_front.hpp b/base/move_to_front.hpp
new file mode 100644
index 0000000000..b4b329c687
--- /dev/null
+++ b/base/move_to_front.hpp
@@ -0,0 +1,25 @@
+#pragma once
+
+#include <array>
+#include <cstdint>
+#include <limits>
+
+namespace base
+{
+class MoveToFront
+{
+public:
+  static size_t constexpr kNumBytes = static_cast<size_t>(std::numeric_limits<uint8_t>::max()) + 1;
+
+  MoveToFront();
+
+  // Returns index of the byte |b| in the current sequence of bytes, then, moves |b|
+  // to the first positions.
+  uint8_t Transform(uint8_t b);
+
+  uint8_t operator[](uint8_t i) const { return m_order[i]; }
+
+private:
+  std::array<uint8_t, kNumBytes> m_order;
+};
+}  // namespace
diff --git a/base/suffix_array.cpp b/base/suffix_array.cpp
index d77a473f78..16d16bd0c1 100644
--- a/base/suffix_array.cpp
+++ b/base/suffix_array.cpp
@@ -33,7 +33,7 @@ void RadixSort(size_t numKeys, size_t const * keys, size_t numValues, Values con
   {
     auto const value = values[keys[i]];
     ASSERT_LESS(value, count.size(), ());
-    ++count[values[keys[i]]];
+    ++count[value];
   }
   for (size_t i = 1; i < numValues; ++i)
     count[i] += count[i - 1];