Tag Archives: xor

Xor delta coding

This post is a (bit modified) translation of my older post in Russian.

Delta coding is widely used as a component of different algorithms e. g. data compression or digital signal processing. Delta encoding is done through computation of differences between adjacent elements of a sequence and hence is the result of applying the first-order finite difference operator, which is a discrete analogue of a continuous differential operator. Delta decoding is done through computation of partial sums and is a discrete analogue of a continuous integration operator.

Delta encoding has the following important feature: a sequence of repeating values produces a sequence of zeroes. That made me ponder what if difference be replaced with something else conserving the mentioned property of converting sequences of repeating values into zeroes. The obvious candidate (for the case when values have fixed-size binary representation) is the bitwise exclusive or operation (xor; do other viable candidates exist?). This operation is commutative and associative. It also has the following properties (for any a):

  • a xor 0 ≡ a;
  • a xor a ≡ 0.

A corollary of this is (a xor b) xor ba for any a and any b. (This is the base of the well-known trick of swapping values of two variables without explicitly using temporary storage.)

Thus for a set of functions defined as { xora | aZ, xora(x) ≡ a xor x } we have an identity element xor0. Any element of this abelian group (with function composition operation) is an inverse to itself.

These properties made xor popular in cryptographic algorithms (is there any well-known cipher or hash that doesn’t use it?).

The following code replaces addition and subtraction in «classic» delta coding algorithm with bitwise xor.

void xor_delta_encode(char *begin, size_t n)
{
  char prev = begin[0], t;
  for (size_t i = 1; i < n; ++i)
  {
    t = begin[i];
    begin[i] ^= prev;
    prev = t;
  }
}
 
void xor_delta_decode(char *begin, size_t n)
{
  char prev = begin[0];
  for (size_t i = 1; i < n; ++i)
    prev = begin[i] ^= prev;
}

Simple testing code is available here.

This code has an amusing property: repeated xor-delta encoding leads to coincidence of prefixes of the resulting sequence and the original sequence. It can be shown on paper (due to properties of xor) that after 2n repeats we have coincidence of prefix of length 2n (or coincidence of the entire sequences if the original sequence is no longer than 2n). Therefore after 2N repeats of encoding, where N = ceil(log2(sequence length)), we have the original sequence recovered. Repeating of the inverse operation (decoding) has the same property and enumerates the same intermediate sequences but in inverse order.

Реклама

Xor-Δ-кодирование

Дельта-кодирование является распространённым составным элементом различных алгоритмов сжатия данных и обработки дискретных сигналов. Дельта-кодирование выполняется путём вычисления разностей между соседними элементами последовательности (и напоминает дифференцирование). Дельта-декодирование выполняется путём накапливания частичных сумм (и напоминает, соответственно, интегрирование).

Одним из характерных свойств дельта-кодирования является то, что последовательность повторяющихся значений кодируется последовательностью нулей. В связи с этим, мне стало интересно, что получится, если заменить и вычитание и сложение одной операцией — вычислением поразрядного исключающего или (xor). Данная операция коммутативна и ассоциативна. Кроме того, она обладает следующими двумя свойствами (для любого числа a):

  • a xor 0 ≡ a;
  • a xor a ≡ 0.

Откуда легко выводится тождество (a xor b) xor b ≡ a.

Таким образом, если мы определим множество функций { xora | a ∈ Z, xora(x) ≡ a xor x }, то единица этого множества — тождественное преобразование xor0, и каждый элемент этого множества является обратным к самому себе относительно операции композиции функций (в частности, множество таких функций является абелевой группой относительно операции композиции).

Благодаря своим свойствам, операция xor очень популярна в области криптографических алгоритмов.

Итак, я написал следующий C++-код, заменяющий операции вычитания и сложения в дельта-кодировании/декодировании на операцию поразрядного исключающего или.

void xor_delta_encode(char *begin, size_t n)
{
  char prev = begin[0], t;
  for (size_t i = 1; i < n; ++i)
  {
    t = begin[i];
    begin[i] ^= prev;
    prev = t;
  }
}

void xor_delta_decode(char *begin, size_t n)
{
  char prev = begin[0];
  for (size_t i = 1; i < n; ++i)
    prev = begin[i] ^= prev;
}

Тестировочный код целиком: Bitbucket.

Если запустить этот код, то можно увидеть довольно забавное свойство (которое и сподвигло меня написать этот пост).

Повторное xor-дельта-кодирование приводит к повторению префиксов исходной последовательности. А именно (это можно показать «на бумажке», сокращая элементы благодаря свойствам операции xor): после 2n повторений имеем совпадение с исходной последовательностью префикса длины до 2n. Через 2N повторений операции кодирования, где N = ceil(log2(длина последовательности)), имеем восстановление исходной последовательности, «круг замкнулся». Повторение обратной операции (xor-дельта-декодирования) перебирает те же 2N возможных последовательностей, но уже в обратном порядке.