RLE圧縮アルゴリズム

ランレングス法とは

データが「何個」同じのが連続してるのか、で圧縮する方法です。

PCXにおけるRLEパケット

PCXの場合は最初に長さ、次にデータの順に格納されてます

パケット構造

とりあえず一バイト読み込んで、それが0xC0以上の値の場合は下位6bitが長さ、次のバイトがデータという構造です。

先頭2bitでRLEの長さデータかを判定する関係上、値が192以上は常にRLE圧縮されることになります。

つまり、パレット画像の場合はパレット番号が192以上の色を使うと場合によってはデータが増えます

展開用コードサンプル

なぜかRuby版

def self.decode(bytes, length)
  buf = []
  off = 0
  while buf.size < length
    byte = bytes[off]; off += 1
    if byte >= 0xC0
      len = byte & 0x3F
      byte = bytes[off]; off += 1
      buf += [byte] * len
    else
      buf << byte
    end
  end
  return buf
end

注意点として、読み込んだデータがファイルヘッダのBytesPerScanlineのサイズになったらそこで行は終了です

圧縮用コードサンプル

def self.encode(bytes)
  packets = []
  byte0 = bytes[0]
  count = 1
  (1...bytes.size).each do |i|
    byte1 = bytes[i]
    if byte0 == byte1
      count += 1
    else
      packets << [count, byte0]
      byte0 = byte1
      count = 1
    end
  end
  packets << [count, byte0]
  buf = []
  packets.each do |packet|
    cnt = packet[0] / 0x3F
    rem = packet[0] % 0x3F
    buf += [0xC0 | 0x3F, packet[1]] * cnt if cnt > 0
    if rem > 0
      if rem == 1 && packet[1] < 0xC0
        buf += [packet[1]]
      else
        buf += [0xC0 | rem, packet[1]]
      end
    end
  end
  return buf.pack('C*')
end

こっちもRuby版 (拙作Rixmapから)