Published on 9 Dec 2010. Tagged with php, algorithmicadvent.
Use this functions to encode data that contains long sequences of the same byte such as barcodes or black-and-white images.
/**
* Encodes the input using a byte-wise run-length algorithm
*
* Example:
*
* $input = str_repeat('A', 1)
* . str_repeat('B', 32)
* . str_repeat('C', 17)
* . str_repeat('D', 517);
*
* echo rle_encode($input);
*
* Outputs a string containing the following bytes:
*
* 01 41 20 42 11 43 FF 44 FF 44 07 44
*
* This translates to:
*
* Amount Byte
* ============
* 1 "A"
* 32 "B"
* 17 "C"
* 255 "D"
* 255 "D"
* 7 "D"
*
* @param string $data String to encode
* @return string Encoded string
*/
function rle_encode($data)
{
$data = (string) $data;
$ret = '';
$len = strlen($data);
$char = '';
$cnt = 0;
for ($i = 0; $i < $len; $i++) {
$c = substr($data, $i, 1);
if ($c !== $char || $cnt === 255) {
if ($char !== '') {
$ret .= chr($cnt) . $char;
}
$char = $c;
$cnt = 1;
} else {
$cnt++;
}
}
if ($char !== '') {
$ret .= chr($cnt) . $char;
}
return $ret;
}
/**
* Decodes a run-length encoded string
*
* See description of rle_encode for details.
*
* @param string $data Run-length encoded string
* @return string Decoded string
*/
function rle_decode($data)
{
$data = (string) $data;
$ret = '';
$len = strlen($data);
if ($len % 2 !== 0) {
throw new Exception('Input data is malformed');
}
for ($i = 0; $i < $len; $i += 2) {
$cnt = substr($data, $i , 1);
$c = substr($data, $i + 1, 1);
$ret .= str_repeat($c, ord($cnt));
}
return $ret;
}
// Test
$input = str_repeat('A', 1)
. str_repeat('B', 32)
. str_repeat('C', 17)
. str_repeat('D', 517);
$rle = rle_encode($input);
if ($input === rle_decode($rle)) {
echo 'Success';
}