解凍処理の内容
主に、二種類の復号処理で解凍出来ます。
- LZ 符号の復号
- ハフマン符号の復号
LZ 符号の復号
次のようなイメージです。
LZ符号の例
LZ符号:
'code length, literal/' {6,16} ' alphabet, distance' {11,19} 'ab' {9,2}
復号処理部 = {文字数, 前方距離}
{ 6,16} -> 'length'
{11,19} -> ' alphabet, '
{ 9, 2} -> 'ababababa'
復号結果:
'code length, literal/length alphabet, distance alphabet, abababababa'
何文字前から、何文字複写する、というだけなので処理内容は簡単です。
ハフマン符号の復号
特定のビット並び（可変長）に対して、文字が割り当てられています。
ハフマン符号の辞書例
辞書:
文字 パターン
' ' 1110
'a' 100
'c' 10100
'd' 1111
'e' 000
'f' 001
'h' 10101
'm' 010
'n' 10110
'o' 10111
'p' 11000
'r' 11001
's' 011
't' 11010
'u' 11011
復号は、例えば 100 のビット列がきたら 'a' の文字に置き換る、という処理を繰り返します。
ハフマン符号の例
ハフマン符号:
10101110110010010101001011011101010010111010110001100100001101100011111110111110011010100
復号結果:
'huffman compressed data'
符号: 10101 11011 001 001 010 100 10110 1110 10100 10111 010 11000 11001 000 011 011 000 1111 1110 1111 100 11010 100
復号: 'h' 'u' 'f' 'f' 'm' 'a' 'n' ' ' 'c' 'o' 'm' 'p' 'r' 'e' 's' 's' 'e' 'd' ' ' 'd' 'a' 't' 'a'
こんな感じです。
解凍プログラム
実行効率は重視していないので、かなり遅いです。
以下、XCode 12.4 の Console アプリとして作った解凍プログラム。
解凍プログラム（短くないので折りたたみ）
main.swift
import Foundation
/**
テーブル参照によるビット列反転
静的関数のみ
- inverse(x,width) : 指定幅のビット列反転
- inverse8(x) : 8 ビットのビット列反転
- inverse16(x) : 16 ビットのビット列反転
*/
struct BitInverse {
/// 8ビット分の変換テーブル
static let table = Array<UInt>(unsafeUninitializedCapacity: 256) {
buffer, size in
for n in 0..<256 {
var x = UInt(n)
let b0: UInt = ((x & 0x80) != 0) ? 0x01 : 0
let b1: UInt = ((x & 0x40) != 0) ? 0x02 : 0
let b2: UInt = ((x & 0x20) != 0) ? 0x04 : 0
let b3: UInt = ((x & 0x10) != 0) ? 0x08 : 0
let b4: UInt = ((x & 0x08) != 0) ? 0x10 : 0
let b5: UInt = ((x & 0x04) != 0) ? 0x20 : 0
let b6: UInt = ((x & 0x02) != 0) ? 0x40 : 0
let b7: UInt = ((x & 0x01) != 0) ? 0x80 : 0
buffer[n] = b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7
}
size = 256
}
/// 下位 8 ビットのビット列反転
/// - Parameter x: 対象値
/// - Returns: ビット列反転値
static func inverse8(_ x: UInt) -> UInt {
return table[Int(x & 0xff)]
}
/// 下位 16 ビットのビット列反転
/// - Parameter x: 対象値
/// - Returns: ビット列反転値
static func inverse16(_ x: UInt) -> UInt {
let v = Int(x & 0xffff)
let l = table[v >> 8]
let h = table[v & 0xff]
return (h << 8) | l
}
/// 指定幅下位ビットのビット列反転
/// - Parameters:
/// - x: 対象値
/// - width: 反転するビット数（上限は 16）
/// - Returns: ビット列反転値
static func inverse(_ x: UInt, _ width: UInt) -> UInt {
return inverse16(x) >> (16 - width)
}
}
/**
Adler-32 算出用
*/
class Adler32 {
/// Adler-32 下位 16 ビット
private var valueL: UInt = 1
/// Adler-32 上位 16 ビット
private var valueH: UInt = 0
/// Adler-32 値
var value: UInt {
get {
return ((valueH << 16) | valueL)
}
}
/// 初期状態にする
func reset() {
valueL = 1
valueH = 0
}
/// 1 バイト分の Adler-32 更新
/// - Parameter x: バイト データ
func update(_ x: UInt8) {
valueL = (valueL + UInt(x)) % 65521
valueH = (valueH + valueL) % 65521
}
}
/**
CRC-32 算出用
*/
class CRC32 {
/// 8 ビット分の演算用テーブル
static let table = Array<UInt>(unsafeUninitializedCapacity: 256) {
buffer, size in
let p = UInt(0xedb88320)
for x in 0..<256 {
var y = UInt(x)
for _ in 0...7 {
y = (y >> 1) ^ (((y & 1) != 0) ? p : 0)
}
buffer[x] = y
}
size = 256
}
/// 内部算出値
private var crc: UInt = 0xffff_ffff
/// CRC-32 値
var value: UInt {
get {
return crc ^ 0xffff_ffff
}
}
/// 初期状態にする
func reset() {
crc = 0xffff_ffff
}
/// 1バイト分の CRC-32 更新
/// - Parameter x: バイト データ
func update(_ x: UInt8) {
crc = (crc >> 8) ^ CRC32.table[Int((crc ^ UInt(x)) & 0xff)]
}
}
/// I/O エラー例外
enum IOError : Error {
/// 読み込み用で開けなかった
case readOpen(String)
/// 読み込みに失敗
case readData(String)
/// データがない
case readEnd(String)
/// 書き込み用で開けなかった
case writeOpen(String)
/// 書き込みに失敗
case writeData(String)
}
/**
バイト データ列の逐次取得用プロトコル
- Requires: 1バイトのデータ取得 : func read() throws -> UInt
*/
protocol InputByteStream {
/// 1バイトのデータ取得
/// - Returns: 1 バイトのデータ
func read() throws -> UInt
}
/**
バイト データ列の逐次出力用プロトコル
- Requires: 1 バイトのデータ出力 : func write(data: Int) throws
*/
protocol OutputByteStream {
/// 1 バイトのデータ出力
/// - Parameter data: 1 バイトのデータ
func write(_ data: UInt8) throws
}
/**
InputByteStream / OutputByteStream 用の小道具
静的関数のみ
+ リトル・エンディアン用
- read16le(stream) : 16 ビット幅のデータを取得
- read32le(stream) : 32 ビット幅のデータを取得
+ ビッグ・エンディアン用
- read16be(stream) : 16 ビット幅のデータを取得
- read32be(stream) : 32 ビット幅のデータを取得
*/
struct ByteStreamUtil {
/// リトル・エンディアン用 16 ビット幅のデータを取得
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
/// - Throws: istream 依存
/// - Returns: リトル・エンディアンの 16 ビット・データ
static func read16le(_ istream: InputByteStream) throws -> UInt {
let l = try istream.read()
let h = try istream.read()
return l | (h << 8)
}
/// リトル・エンディアン用 32 ビット幅のデータを取得
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
/// - Throws: istream 依存
/// - Returns: リトル・エンディアンの 32 ビット・データ
static func read32le(_ istream: InputByteStream) throws -> UInt {
let l = try ByteStreamUtil.read16le(istream)
let h = try ByteStreamUtil.read16le(istream)
return l | (h << 16)
}
/// ビッグ・エンディアン用 16 ビット幅のデータを取得
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
/// - Throws: istream 依存
/// - Returns: ビッグ・エンディアンの 16 ビット・データ
static func read16be(_ istream: InputByteStream) throws -> UInt {
let h = try istream.read()
let l = try istream.read()
return (h << 8) | l
}
/// ビッグ・エンディアン用 32 ビット幅のデータを取得
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
/// - Throws: istream 依存
/// - Returns: ビッグ・エンディアンの 32 ビット・データ
static func read32be(_ istream: InputByteStream) throws -> UInt {
let h = try ByteStreamUtil.read16be(istream)
let l = try ByteStreamUtil.read16be(istream)
return (h << 16) | l
}
}
/**
ファイルからバイト データ列の逐次取得
*/
class InputByteStreamFile : InputByteStream {
/// ファイル名
var name: String
/// 入力ストリーム
private var stream: InputStream
/// 初期化
/// - Parameter path: パス名
/// - Throws: IOErrpr.readOpen
init(_ path: String) throws {
guard let s = InputStream(fileAtPath: path) else {
throw IOError.readOpen(path)
}
s.open()
name = path
stream = s
}
/// 1 バイトの読み取り
/// - Throws: IOError.readData, IOError.readEnd
/// - Returns: 1 バイトのデータ
func read() throws -> UInt {
var buffer = [UInt8(0)]
let res = stream.read(&buffer, maxLength: 1)
if res < 0 {
throw IOError.readData(name)
}
if res != 1 {
throw IOError.readEnd(name)
}
return UInt(buffer[0])
}
}
/**
バイト データ列の逐次取得と CRC-32 の算出
*/
class InputByteStreamCRC32 : InputByteStream {
/// バイト列の入力元
private let input: InputByteStream
/// CRC-32 算出用
private let crc = CRC32()
/// CRC-32 値
var crc32 : UInt {
get {
return crc.value
}
}
/// 初期化
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
init(_ istream: InputByteStream) {
input = istream
}
/// 1 バイトの読み取りと CRC-32 の更新
/// - Throws: input 依存
/// - Returns: 1 バイトのデータ
func read() throws -> UInt {
let data = try input.read()
crc.update(UInt8(data))
return data
}
}
/**
InputByteStream を使ったビット単位でのデータを取得
*/
class InputBitStream {
/// 一時的なビット データのバッファ
private var data: UInt = 0
/// data で保持されているビット数
private var size: UInt = 0
/// InputByteStream プロトコル実装オブジェクト
let input: InputByteStream
/// 初期化
/// - Parameter istream: InputByteStream プロトコル実装オブジェクト
init(_ istream: InputByteStream) {
input = istream
}
/// バイト境界までのデータを破棄する
func align() {
let gap = size & 7
data >>= gap
size -= gap
}
/// 指定ビット数のデータを取得する
/// - Parameter width: ビット数（最大 16 ビット）
/// - Throws: input 依存
/// - Returns: 指定ビット数のデータ
func read(_ width: UInt) throws -> UInt {
while size < width {
let d = try input.read()
data |= d << size
size += 8
}
let value = data & ((1 << width) - 1)
data >>= width
size -= width
return value
}
}
/**
ファイルを全て読み込む方式の InputByteStream
*/
class FileReadAll : InputByteStream {
/// ファイル名
let name: String
/// ファイルの全データ
let data: Data
/// InputByteStream 用データ位置
var position: Data.Index = 0
/// 初期化 :ファイルを全て読み込む
/// - Parameter path: パス名
/// - Throws: IOError.readOpen, IOError.readData および FileManager 依存
init(_ path: String) throws {
guard let contents = FileManager().contents(atPath: path) else {
throw IOError.readOpen(path)
}
name = path
data = contents
}
/// InputByteStream.read の実装
/// - Throws: IOError.readEnd
/// - Returns: 1 バイトのデータ
func read() throws -> UInt {
if position < data.count {
let value = data[position]
position += 1
return UInt(value)
}
throw IOError.readEnd(name)
}
}
/**
メモリ上に解凍データを保持
*/
class OutputByteStreamMemory : OutputByteStream {
/// 解凍データ
var data = Data()
/// OutputByteStream.write の実装
/// - Parameter byteData: 出力データ
/// - Throws: なし
func write(_ byteData: UInt8) throws {
data.append(byteData)
}
/// 解凍データをファイルへ出力
/// - Parameter path: パス名
/// - Throws: IOError.writeOpen および FileManager 依存
func writeToFile(_ path: String) throws {
if !FileManager().createFile(atPath: path, contents: data) {
throw IOError.writeOpen(path)
}
}
}
/**
ファイルへバイト データ列を逐次出力
*/
class OutputByteStreamFile : OutputByteStream {
/// ファイル名
var name: String
/// 出力ストリーム
private var stream: OutputStream
/// 初期化
/// - Parameter path: パス名
/// - Throws: IOError.writeOpen
init(_ path: String) throws {
guard let s = OutputStream(toFileAtPath: path, append: false) else {
throw IOError.writeOpen(path)
}
s.open()
name = path
stream = s
}
/// 1 バイトの書き込み
/// - Parameter data: 1 バイトの出力データ
/// - Throws: FileHandle 依存
func write(_ data: UInt8) throws {
var byte = data
let res = stream.write(&byte, maxLength: 1)
if res != 1 {
throw IOError.writeData(name)
}
}
}
/**
バイト データ列の逐次出力と Adler-32 の算出
*/
class OutputByteStreamAdler32 : OutputByteStream {
/// バイト列の出力先
let output: OutputByteStream
/// Adler-32 算出用
private var adler = Adler32()
/// Adler-32 値
var adler32 : UInt {
get {
return adler.value
}
}
/// 初期化
/// - Parameter ostream: OutputByteStream プロトコル実装オブジェクト
init(_ ostream: OutputByteStream) {
output = ostream
}
/// 1 バイトの出力と Adler-32 の更新
/// - Parameter byteData: 1 バイトの出力データ
/// - Throws: output 依存
func write(_ byteData: UInt8) throws {
try output.write(byteData)
adler.update(byteData)
}
}
/**
バイト データ列の逐次出力と CRC-32 の算出
*/
class OutputByteStreamCRC32 : OutputByteStream {
/// バイト列の出力先
let output: OutputByteStream
/// CRC-32 算出用
private var crc = CRC32()
/// CRC-32 値
var crc32 : UInt {
get {
return crc.value
}
}
/// 解凍サイズ
var isize: UInt = 0
/// 初期化
/// - Parameter ostream: OutputByteStream プロトコル実装オブジェクト
init(_ ostream: OutputByteStream) {
output = ostream
}
/// 1 バイトのデータ出力と CRC-32 および出力サイズの更新
/// - Parameter byteData: 1 バイトの出力データ
/// - Throws: output 依存
func write(_ byteData: UInt8) throws {
try output.write(byteData)
crc.update(byteData)
isize += 1
}
}
/**
LZ 復号出力
"文字" または "{長さ,距離}" 形式の出力を実行します
*/
class OutputLZStream {
/// LZ 複写用窓
private var window = Data(count: 0x8000)
/// 窓中の位置
private var position = 0
/// 窓アクセス時のインデックス範囲マスク
private var mask = 0x7fff
/// バイト列の出力先
let output: OutputByteStream
/// 初期化
/// - Parameter ostream: OutputByteStream プロトコル実装オブジェクト
init(_ ostream: OutputByteStream) {
output = ostream
}
/// 1 バイト（文字）のデータ出力と LZ 複写用窓の更新
/// - Parameter literal: 文字
/// - Throws: output 依存
func write(_ literal: UInt8) throws {
try output.write(literal)
window[position] = literal
position = (position + 1) & mask
}
/// LZ 符号 "{長さ,距離}" での複写出力
/// - Parameters:
/// - length: 長さ
/// - distance: 距離
/// - Throws: output 依存
func write(_ length: UInt, _ distance: UInt) throws {
var offset = (position - Int(distance)) & mask
for _ in 0..<length {
try write(window[offset])
offset = (offset + 1) & mask
}
}
}
/**
動的辞書またはハフマン復号の例外
*/
enum HuffmanDecodeError : Error {
/// 符号長辞書エラー
case length
// 文字（長）辞書エラー
case literal
// 距離辞書エラー
case distance
}
/**
ハフマン復号用プロトコル
- Requires: 復号： func decode(stream: InputBitStream) throws -> UInt
*/
protocol HuffmanDecoder {
func decode(_ stream: InputBitStream) throws -> UInt
}
/**
文字（長）用固定辞書のハフマン復号
*/
class FixedLiteralHuffmanDecoder : HuffmanDecoder {
/// ビット列から文字（長）を復号
/// - Parameter stream: ビット列の入力元
/// - Throws: stream 依存
/// - Returns: 復号文字（長）
func decode(_ stream: InputBitStream) throws -> UInt {
var code = BitInverse.inverse(try stream.read(7), 7)
if code < 0x18 {
return code + 256
}
code = (code << 1) | (try stream.read(1))
if code < 0xc0 {
return code - 0x30
}
if code < 0xc8 {
return code - 0xc0 + 280
}
code = (code << 1) | (try stream.read(1))
return code - 0x190 + 144
}
}
/**
距離情報用固定辞書のハフマン復号
*/
class FixedDistanceHuffmanDecoder : HuffmanDecoder {
/// ビット列から距離情報を復号
/// - Parameter stream: ビット列の入力元
/// - Throws: stream 依存
/// - Returns: 復号距離情報
func decode(_ stream: InputBitStream) throws -> UInt {
return BitInverse.inverse8((try stream.read(5)) << 3)
}
}
/**
動的辞書のハフマン復号
*/
class DynamicHuffmanDecoder : HuffmanDecoder {
/// 符号長に対する文字（長）一覧
private class LengthInfo {
/// 符号長
var length: UInt = 0
/// LengthInfo 一覧における直前の length との差
var lengthStep: UInt = 0
/// 符号範囲の開始
var codeStart: UInt = 0
/// 符号範囲の終了 + 1
var codeEnd: UInt = 0
/// 文字の一覧
private var literals: [UInt] = []
/// 文字の数
var count: UInt {
get {
return UInt(literals.count)
}
}
/// 初期化
/// - Parameter width: 符号長
init(_ width: UInt) {
length = width
}
/// 文字を追加
/// - Parameter literal: 文字
func append(_ literal: UInt) {
literals.append(literal)
}
subscript(_ index: UInt) -> UInt {
return literals[Int(index)]
}
}
/// LengthInfo の表
private var table: [LengthInfo] = []
/// 例外オブジェクト
let error: HuffmanDecodeError
/// 初期化
/// - Parameters:
/// - maxLength: ハフマン符号の最大長
/// - errcode: 例外オブジェクト
init(_ maxLength: UInt, _ errcode: HuffmanDecodeError) {
error = errcode
for n in 0...maxLength {
table.append(LengthInfo(n))
}
}
/// 文字（長）と、符号長を設定する
/// - Parameters:
/// - length: 符号長（ビット数）
/// - literal: 文字（長）
func set(_ length: UInt, _ literal: UInt) {
if length > 0 {
table[Int(length)].append(literal)
}
}
/// 文字（長）と、符号長を設定して、復号の準備をする
/// - Parameter lengths: 符号長一覧
/// - Throws: error 依存
func set(_ lengths: [UInt]) throws {
for literal in 0..<lengths.count {
set(lengths[literal], UInt(literal))
}
try prepareDecode()
}
/// 文字（長）と、符号長を設定して、復号の準備をする
/// - Parameter lengths: 符号長一覧
/// - Throws: error 依存
func set(_ lengths: ArraySlice<UInt>) throws {
let start = lengths.startIndex
for literal in 0..<lengths.count {
set(lengths[literal + start], UInt(literal))
}
try prepareDecode()
}
/// 復号の準備
/// - Throws: HuffmanDecodeError
func prepareDecode() throws {
var newTable: [LengthInfo] = []
for li in table {
if li.count != 0 {
newTable.append(li)
}
}
if newTable.count == 0 {
throw error
}
table = newTable
var last: UInt = 0
var code: UInt = 0
for li in table {
let length = li.length
let count = li.count
let step = length - last
let start = code << step
let end = start + count
li.lengthStep = step
li.codeStart = start
li.codeEnd = end
last = length
code = end
}
if code > (1 << last) {
throw error
}
}
/// 復号
/// - Parameter stream: ビット列の入力元
/// - Throws: HuffmanDecodeError
/// - Returns: 復号した情報
func decode(_ stream: InputBitStream) throws -> UInt {
var pending: UInt = 0
var code: UInt = 0
for li in table {
let step = li.lengthStep
let start = li.codeStart
let end = li.codeEnd
code <<= step
pending += step
if code < end {
code |= BitInverse.inverse(try stream.read(pending), pending)
if code < end {
return li[code - start]
}
pending = 0
}
}
throw error
}
}
/**
圧縮ブロック解凍時の例外
*/
enum InflateBlockError : Error {
case btype // BTYPE=11
case btype00Len(UInt, UInt) // LEN != ~NLEN
case btype10Length // 動的辞書復号エラー
case btype10Literal // 文字（長）の動的辞書エラー
case btype10Distance // 距離の動的辞書エラー
}
/**
圧縮ブロックの解凍
*/
class InflateBlock {
/// 圧縮ブロックの全体を解凍
/// - Parameters:
/// - istream: 入力元（バイト列）
/// - ostream: 出力先
/// - Throws: HuffmanDecodeError, InflateBlockError および istream, ostream 依存
static func inflate(_ istream: InputByteStream, _ ostream: OutputByteStream) throws {
let input = InputBitStream(istream)
let output = OutputLZStream(ostream)
var bfinal = false
while !bfinal {
bfinal = (try input.read(1) != 0)
let btype = try input.read(2)
switch btype {
case 0:
try blockType00(input, output)
case 1:
try blockType01(input, output)
case 2:
try blockType10(input, output)
default:
throw InflateBlockError.btype
}
}
input.align()
}
/// BTYPE=00 （非圧縮）の処理
/// - Parameters:
/// - input: 入力元（ビット列）
/// - output: 出力先（LZ 符号）
/// - Throws: input, output 依存
private static func blockType00(_ input: InputBitStream, _ output: OutputLZStream) throws {
input.align()
let len = try input.read(16)
let nlen = try input.read(16)
if len != (nlen ^ 0xffff) {
throw InflateBlockError.btype00Len(len, nlen)
}
for _ in 1...len {
try output.write(UInt8(try input.read(8)))
}
}
/// BTYPE=01 （固定辞書による圧縮）の解凍
/// - Parameters:
/// - input: 入力元（ビット列）
/// - output: 出力先（LZ 符号）
/// - Throws: HuffmanDecodeError, InflateBlockError および input, output 依存
private static func blockType01(_ input: InputBitStream, _ output: OutputLZStream) throws {
try blockData(input, output, FixedLiteralHuffmanDecoder(), FixedDistanceHuffmanDecoder())
}
/// BTYPE=10 用テーブル
private static let btype10LengthOrder = [
16, 17, 18,
0, 8, 7, 9, 6, 10, 5, 11,
4, 12, 3, 13, 2, 14, 1, 15,
]
/// BTYPE=10 （動的辞書による圧縮）の解凍
/// - Parameters:
/// - input: 入力元（ビット列）
/// - output: 出力先（LZ 符号）
/// - Throws: HuffmanDecodeError, InflateBlockError および input, output 依存
private static func blockType10(_ input: InputBitStream, _ output: OutputLZStream) throws {
let lengthDecoder = DynamicHuffmanDecoder(7, HuffmanDecodeError.length)
let literalDecoder = DynamicHuffmanDecoder(15, HuffmanDecodeError.literal)
let distanceDecoder = DynamicHuffmanDecoder(15, HuffmanDecodeError.distance)
let hlit = try input.read(5) + 257
let hdist = try input.read(5) + 1
let hclen = try input.read(4) + 4
var codeLength = Array<UInt>(repeating: 0, count: 19)
for hcindex in 0..<Int(hclen) {
codeLength[btype10LengthOrder[hcindex]] = try input.read(3)
}
try lengthDecoder.set(codeLength)
let lengths = try dynamicDictionary(input, lengthDecoder, hlit + hdist)
try literalDecoder.set(lengths[0..<Int(hlit)])
try distanceDecoder.set(lengths[Int(hlit)...])
try blockData(input, output, literalDecoder, distanceDecoder)
}
/// 動的辞書の生成
/// - Parameters:
/// - input: 入力元（ビット列）
/// - lengthDecoder: 符号長の復号辞書
/// - count: 文字（長）の数
/// - error: エラー時の例外
/// - Throws: error で指定
/// - Returns: 符号長一覧
private static func dynamicDictionary(
_ input: InputBitStream,
_ lengthDecoder: HuffmanDecoder,
_ count: UInt
) throws -> [UInt] {
var output: [UInt] = []
var literal: UInt = 0
var last: UInt = 0
while literal < count {
let length = try lengthDecoder.decode(input)
var repcnt: UInt = 0
switch length {
case 0...15:
output.append(length)
last = length
literal += 1
continue
case 16:
repcnt = 3 + (try input.read(2))
case 17:
repcnt = 3 + (try input.read(3))
last = 0
case 18:
repcnt = 11 + (try input.read(7))
last = 0
default:
throw InflateBlockError.btype10Length
}
literal += repcnt
if literal > count {
throw InflateBlockError.btype10Length
}
for _ in 1...repcnt {
output.append(last)
}
}
return output
}
/// 圧縮データの解凍
/// - Parameters:
/// - input: 入力元（ビット列）
/// - output: 出力先（LZ 符号）
/// - literalDictionary: 文字（長）の辞書
/// - distanceDictionary: 距離の辞書
/// - Throws: HuffmanDecodeError, InflateBlockError および input, output 依存
private static func blockData(
_ input: InputBitStream,
_ output: OutputLZStream,
_ literalDictionary: HuffmanDecoder,
_ distanceDictionary: HuffmanDecoder
) throws {
while true {
let literal = try literalDictionary.decode(input)
var length: UInt = 0
switch literal {
case 0...255:
try output.write(UInt8(literal))
continue
case 256:
return
case 257...264:
length = literal - 257 + 3
case 265...284:
let lenCode = literal - 261
let lenBits = lenCode >> 2
let lenBase = (lenCode & 3) + 4
length = 3 + (lenBase << lenBits) + (try input.read(lenBits))
break
case 285:
length = 258
default:
throw HuffmanDecodeError.literal
}
var distance = try distanceDictionary.decode(input)
switch (distance) {
case 0...3:
distance += 1
case 4...29:
let distCode = distance - 2
let distBits = distCode >> 1
let distBase = (distCode & 1) + 2
distance = 1 + (distBase << distBits) + (try input.read(distBits))
default:
throw HuffmanDecodeError.distance
}
try output.write(length, distance)
}
}
}
/**
ZLIB 圧縮データ形式解凍時の例外
*/
enum ZLIBInflateError : Error {
case cm(UInt) // 未知の圧縮形式
case cminfo(UInt) // CMINFO エラー
case fdict // FDICT エラー
case fcheck(UInt) // FCHECK エラー
case adler32(UInt, UInt) // Adler-32 不一致
}
/**
ZLIB 圧縮データ形式の解凍
*/
class ZLIBInflate {
/// 圧縮形式と付随情報
let cmf: UInt
/// FLaGs: フラグ類
let flg: UInt
/// Adler-32 値
let adler32: UInt
/// ZLIB 圧縮形式の解凍
/// - Parameters:
/// - input: 入力元
/// - output: 出力先
/// - Throws: HuffmanDecodeError, InflateBlockError, ZLIBInflateError および input, output 依存
init(_ input: InputByteStream, _ output: OutputByteStream) throws {
cmf = try input.read()
if (cmf & 0x0f) != 8 {
throw ZLIBInflateError.cm(cmf & 0x0f)
}
if (cmf >> 4) >= 8 {
throw ZLIBInflateError.cminfo(cmf >> 4)
}
flg = try input.read()
if (flg & 0x20) != 0 {
throw ZLIBInflateError.fdict
}
let fcheck = cmf * 256 + flg
if (fcheck % 31) != 0 {
throw ZLIBInflateError.fcheck(fcheck)
}
let ostream = OutputByteStreamAdler32(output)
try InflateBlock.inflate(input, ostream)
adler32 = try ByteStreamUtil.read32be(input)
if adler32 != ostream.adler32 {
throw ZLIBInflateError.adler32(adler32, ostream.adler32)
}
}
}
/**
GZIP 圧縮データ形式解凍時の例外
*/
enum GZIPInflateError : Error {
case id1(UInt) // 未知の ID1
case id2(UInt) // 未知の ID2
case cm(UInt) // 未知の圧縮形式
case hcrc(UInt, UInt) // HCRC 不一致
case crc32(UInt, UInt) // CRC32 不一致
case isize(UInt, UInt) // ISIZE 不一致
}
/**
GZIP 圧縮データ形式の解凍
*/
class GZIPInflate {
/// ID1
let id1: UInt
/// ID2
let id2: UInt
/// Compression Method
let cm: UInt
/// FLaGs
let flg: UInt
/// MTIME
let mtime: UInt
/// eXtra FLags
let xfl: UInt
/// OS
let os: UInt
/// FLG.FEXTRA=1 : 拡張情報
let extra: Array<UInt8>
/// FLG.FNAME=1 : 名前
let name: String
/// FLG.FCOMMENT=1 : コメント
let comment: String
/// FLG.FHCRC=1 : ヘッダ部の CRC32 下位 16 ビット
let hcrc: UInt
/// CRC-32 値
let crc32: UInt
/// 元データ（解凍）サイズ
let isize: UInt
/// ZLIB 圧縮形式の解凍
/// - Parameters:
/// - input: 入力元
/// - output: 出力先
/// - Throws: HuffmanDecodeError, InflateBlockError, GZIPInflateError および input, output 依存
init(_ input: InputByteStream, _ output: OutputByteStream) throws {
let istream = InputByteStreamCRC32(input)
id1 = try istream.read()
if id1 != 0x1f {
throw GZIPInflateError.id1(id1)
}
id2 = try istream.read()
if id2 != 0x8b {
throw GZIPInflateError.id1(id1)
}
cm = try istream.read()
if cm != 8 {
throw GZIPInflateError.id1(id1)
}
flg = try istream.read()
mtime = try ByteStreamUtil.read32le(istream)
xfl = try istream.read()
os = try istream.read()
var newExtra = Array<UInt8>()
if (flg & 0x04) != 0 {
for _ in 1...(try ByteStreamUtil.read16le(istream)) {
newExtra.append(UInt8(try istream.read()))
}
}
extra = newExtra
var newName = ""
if (flg & 0x08) != 0 {
while true {
let c = try istream.read()
if c == 0 {
break
}
newName += String(c)
}
}
name = newName
var newComment = ""
if (flg & 0x10) != 0 {
while true {
let c = try istream.read()
if c == 0 {
break
}
newComment += String(c)
}
}
comment = newComment
let sum16 = istream.crc32 & 0xffff
var crc16 = sum16
if (flg & 0x02) != 0 {
crc16 = try ByteStreamUtil.read16le(istream)
if crc16 != sum16 {
throw GZIPInflateError.hcrc(crc16, sum16)
}
}
hcrc = crc16
let ostream = OutputByteStreamCRC32(output)
try InflateBlock.inflate(input, ostream)
crc32 = try ByteStreamUtil.read32le(istream)
let sum32 = ostream.crc32
if crc32 != sum32 {
throw GZIPInflateError.crc32(crc32, sum32)
}
isize = try ByteStreamUtil.read32le(istream)
if isize != ostream.isize {
throw GZIPInflateError.isize(isize, ostream.isize)
}
}
}
/*
gzip 形式の解凍処理
*/
// ファイルをメモリ上に読み込み、メモリ上に解凍してファイルへ書き込む
func gunzipMemory(_ input_file: String, _ output_file: String) throws {
let istream = try FileReadAll(input_file)
let ostream = OutputByteStreamMemory()
let _ = try GZIPInflate(istream, ostream)
try ostream.writeToFile(output_file)
}
// ファイルへのアクセスは、解凍処理中に行う
func gunzipDirect(_ input_file: String, _ output_file: String) throws {
let istream = try InputByteStreamFile(input_file)
let ostream = try OutputByteStreamFile(output_file)
let _ = try GZIPInflate(istream, ostream)
}
/*
gzip 形式の解凍処理
*/
func gunzip(_ input_file:String, _ output_file: String, _ method: (String, String) throws -> Void) -> Bool {
do {
try method(input_file, output_file)
return true
} catch is HuffmanDecodeError {
print("error: Corrupted BTYPE=10: \(input_file)")
} catch InflateBlockError.btype {
print("error: BTYPE=11: : \(input_file)")
} catch InflateBlockError.btype00Len(let len, let nlen) {
print("error: BTYPE=00: \(len) != \(nlen ^ 0xffff): : \(input_file)")
} catch InflateBlockError.btype10Length,
InflateBlockError.btype10Literal,
InflateBlockError.btype10Distance {
print("error: Corrupted BTYPE=10: \(input_file)")
} catch GZIPInflateError.id1(let id1) {
print("error: id1=\(id1): \(input_file)")
} catch GZIPInflateError.id2(let id2) {
print("error: id2=\(id2): \(input_file)")
} catch GZIPInflateError.cm(let cm) {
print("error: cm=\(cm): \(input_file)")
} catch GZIPInflateError.hcrc(let hcrc, let xcrc) {
print("error: hcrc: \(hcrc) != \(xcrc): \(input_file)")
} catch GZIPInflateError.crc32(let crc32, let xcrc) {
print("error: crc32: \(crc32) != \(xcrc): \(input_file)")
} catch GZIPInflateError.isize(let isize, let xsize) {
print("error: isize: \(isize) != \(xsize): \(input_file)")
} catch IOError.readOpen(let name) {
print("error: open: \(name)")
} catch IOError.readData(let name) {
print("error: read: \(name)")
} catch IOError.readEnd(let name) {
print("error: not enough data: \(name)")
} catch IOError.writeOpen(let name) {
print("error: open: \(name)")
} catch IOError.writeData(let name) {
print("error: read: \(name)")
} catch {
print("error: \(error)")
}
return false
}
/*
以下、コマンド・ライン処理
*/
class CommandLineParser {
var cmd_args = CommandLine.arguments
let program_path: String
let description = [
"Usage: \(String(CommandLine.arguments[0].split(separator: "/").last!)) " +
"[options] input_file output_file",
"",
"options are:",
" -D set direct mode.",
" -M set memory mode.",
]
var args = [String]()
var option: [String: Any] = [
"D" : false,
"M" : true,
]
enum OptionError : Error {
case unknown(String)
case invalid(String)
}
init() throws {
program_path = cmd_args.removeFirst()
do {
try parse_args()
} catch OptionError.invalid(let name) {
print("bug: invalid option '\(name)' parameter")
} catch OptionError.unknown(let name) {
print("unknown option: \(name)")
usage()
}
}
func parse_args () throws {
while cmd_args.count != 0 {
var arg = cmd_args.removeFirst()
if arg.count == 0 {
continue
}
if arg.first != "-" {
args.append(arg)
continue
}
arg.removeFirst()
if arg.count == 0 {
args.append("-")
continue
}
if arg.first != "-" {
try parse_short_option(arg)
continue
}
arg.removeFirst()
try parse_long_option(arg)
}
}
func parse_short_option(_ opts: String) throws {
var arg = opts
while arg.count != 0 {
let key = String(arg.removeFirst())
try update_option("-", key)
}
}
func parse_long_option(_ name: String) throws {
if let index = name.firstIndex(of: "=") {
let key = String(name[name.startIndex ..< index])
let value = String(name[name.index(after: index)...])
try update_option("--", key, value)
} else {
try update_option("--", name)
}
}
func update_option(_ prefix: String, _ key: String, _ opt: String? = nil) throws {
let val = option[key]
if val == nil {
throw OptionError.unknown(prefix + key)
}
switch val {
case is Bool:
option[key] = !(val as! Bool)
case is Int:
option[key] = Int(next_arg(opt))
case is String:
option[key] = next_arg(opt)
default:
throw OptionError.invalid(prefix + key)
}
}
func next_arg(_ opt: String?) -> String {
return (opt == nil) ? args.removeFirst() : opt!
}
func usage() -> Never {
for line in description {
print(line)
}
exit(1)
}
}
func main() -> Never {
let cmdline = try! CommandLineParser()
var args = cmdline.args
if args.count != 2 {
cmdline.usage()
}
let input_file = args.removeFirst()
let output_file = args.removeFirst()
if cmdline.option["D"] as! Bool {
exit(gunzip(input_file, output_file, gunzipDirect(_:_:)) ? 0 : 1)
}
exit(gunzip(input_file, output_file, gunzipMemory(_:_:)) ? 0 : 1)
}
main()
データ形式の詳細は、Python 版の記事などを参照してください。