lynxeyedの電音鍵盤

MBDとFPGAと車載で使うデバイスの備忘録

少ないメモリーで動作できる可逆圧縮形式を作る

Lossless

最近組み込みCPUの処理速度、メモリといった性能が向上しているのでMP3デコーダを実装するのが流行りの様です。それも面白いのですが、ま、MP3プレーヤとかもう持ってるよ、みたいな。笑

ほぼ思いつきなのですが、ちょっとこのブログではひねくれてみて可逆圧縮形式のフォーマット対応プレーヤを作ろうと思いました。
自分が欲しいと思う機能に録音機能(ダイレクトエンコーディング機能)があるのでそれにも対応します。
簡単な話、手軽なDATが欲しいと思いたった訳です。

最近ではSDカードやHDDの大容量・低価格化に伴い非可逆圧縮でない高音質な音声フォーマット形式も見直されてきています。
始めは、現時点で存在する比較的有名な可逆圧縮方式を採用しようと思っていました。具体的には以下の形式です。

別個に符号化形式も概要を調べてみました

  • Huffman符号化
  • Range Coder
  • Rice Golomb 符号化

詳細はWikipediaや詳しく扱われている書物、HPに委ねますが、特定の音声フォーマットに準拠するのはハードルが高いと思いました。
理由としまして、PCでのエンコーディングを想定しており、処理用のメモリーを外部に数十〜百kBほど増設する必要があります。
TTAに関しては、移植性が一番高そうでしたが、やはりフレーム処理用のメモリー(およそ１秒分のメモリ)という問題があり断念しました。

それならば自分でこしらえる必要があります。(ｼｮｳｷｶﾖ

  • まずハフマン符号化は却下。再生時はデコードの負荷が軽いですが、ダイレクトエンコーディングには向かない。符号化の為の辞書を作るのに膨大なメモリーを要する。ある程度出現率を予測して決め打ちで辞書を作成する事もできるが、平均的サンプル収集ために労力を使いたくない。
  • RangeCoderはすごく面白いのですが、2^24バイトを超えたところで確率表を捨てたり、いろいろからくりが理解できず途中で凍結しました。
  • Rice-Golomb。これはFLACやMonkey's Audioも採用している符号化で比較的高速にエンコード・デコードが可能です。データの絶対値が小さいほど情報量の圧縮が可能です。

RiceGolomb符号化プロセスはMonkey's AudioのTheoryセクションの通りに実装する事にしました。
今回はベタにDPCMをRice-Golomb符号化して圧縮率を確認しました。
実装に伴い、一番面倒だったビット詰めのライブラリをひそかにぐあんをめぐらしての無所属様のブログから拝借したものを改悪して使っています(_bitio.c)。感謝です。
メイン処理は無所属様のお陰で凄く簡単になりました。このほかに_bitio.hで変数宣言を行っています。

/*	Rice Golomb Codings	*/
/*	encode example		*/
#include <stdio.h>
#include <string.h>
#include "_bitio.h"
#include "_bitio.c"
#define k 0x0b //	k:0x09 to 0x0b?		

//  fopenに使うoutfp infpは_bitio.h側で宣言している

//	
//	encoding processes
//	1. sign(1 for positive, 0 for negative)
//	2. n/(2^k) 0&#39;s
//	3. terminating "1"
//	4. k least significant bits of n
//


void encode(long int n){
	int zero_shift = 0;
	
	if(n < 0){
		putbit(0);					// sign (put 0:if n as negative)
		n = -n;						// n = abs(n)
		//printf("\t 0");
	}
	else{ 
		putbit(1);					// sign (put 1:if n as positive)
		//printf("\t 1");
	}
	zero_shift = (n >> (k));
	//printf("\t shift= %d",zero_shift);
	while(zero_shift > 0){

		zero_shift--;
		putbit(0);
	}	// put n/(2^k) 0&#39;s
	
	putbit(1);						// terminating "1"
	putbits(k,rightbits(k,n));
	//printf("\t finish= %d \r\n",(n & ((1U<<k)-1)));
}



void decode(void){
	long int decode_buff;
	long int diff,diff2;
	unsigned int buff_sign,zero_shift;
	char flag;

	diff = 0;
	diff2 = 0;
	// get sign(1 for positive, 0 for negative)
	while((buff_sign = getbit())!=OVERRUN){
	
		zero_shift = 0;
		while(getbit()==0)zero_shift++;
		
		decode_buff = (signed int)((1U << k)*zero_shift);
		decode_buff += (getbits(k));
		
		if(!buff_sign)decode_buff =- decode_buff;
		/* return decode_buff; */
		diff =(diff + decode_buff);
		fwrite(&diff, sizeof(short int), 1, outfp);
		
		
		//diff2 = diff; //for test
		
		if((buff_sign = getbit())==OVERRUN)break;
		zero_shift = 0;
		while(getbit()==0)zero_shift++;
		
		decode_buff = (signed int)((1U << k)*zero_shift);
		decode_buff += (getbits(k));
		
		if(!buff_sign)decode_buff =- decode_buff;
		/* return decode_buff; */
		diff2 =(diff2 + decode_buff);
		fwrite(&diff2, sizeof(short int), 1, outfp);
		
	
 		
	}
}

int main() {
	
	long int diff,diff2;
	signed short int old,old2;
    signed short int s[2];
	int i;
	
    init_bit_o();
	init_bit_i();
	old = 0;
	old2 = 0;
	
	/* encode */
    if ( NULL == (infp = fopen( "test.wav", "rb" )) ) {
        printf( "\r\nError: The message file cannot be accessed\r\n" );
        return -1;
    }
	
	if ( NULL == (outfp = fopen( "test.rgm", "wb" )) ) {
        printf( "\r\nError: The message file cannot be accessed\r\n" );
        return -1;
    }
	
	
	while((fread(&s, sizeof(short int), 2/*10*/, infp))!=0){
		//for(i=0;i<10;i++){
		
		diff = (s[0] - old);
		encode(diff);
		old = s[0];
		
		//old2 = old; //for test
		
		//fread(&s,sizeof(short int),1,infp);
		   
		diff2 = (s[1] - old2);
		encode(diff2);
		old2 = s[1];
		

	}

	fclose( infp );
	fclose( outfp ); 
	
	printf("\tencode finish\r\n");
	/* decode */
	if ( NULL == (infp = fopen( "test.rgm", "rb" )) ) {
        printf( "\r\nError: The message file cannot be accessed\r\n" );
        return -1;
    }
	
	if ( NULL == (outfp = fopen( "decode.wav", "wb" )) ) {
        printf( "\r\nError: The message file cannot be accessed\r\n" );
        return -1;
    }

	
	decode();
		
	
	
	
	fclose( infp );
	fclose( outfp ); 
	
	
}

これをrice_golomb.cという名前で保存。macのgccでコンパイル。
ちなみに#define k 0x09はMonkey's AudioのHPで言及されている定数kと同じ。これが圧縮率を左右する。

$      gcc rice_golomb.c -o rice_golomb

16bit,ステレオのwavファイル(サンプリング周波数は問わない)を用意し、test.wavにリネームし、rice_golombの実行ファイルと同じフォルダにコピー。

$     ./rice_golomb

しばらく待つと、test.rgm(エンコードファイル)とdecode.wav(再デコードファイル)が生成されます。
test.rgmと元ファイルの容量を比較して圧縮率を見る。DPCMだから前回のPCMデータとの差分を取っているだけなので、差分絶対値が小さければ圧縮率は高まり、大きいとあまり圧縮できません。例えば方形波だと圧縮できず逆に膨張してしまいます。
静かなクラシックだとそこそこ圧縮できましたが、ハードロックは予想通り圧縮率は良くありませんでした。
例えばこの曲。『ドヴォルザーク: Symphony #9 "新世界より" - 1. Adagio, Allegro Molto』
元ファイル:53.9MB(=53945650byte)
エンコードファイル:39.5MB(=39471219byte)

圧縮比:73.2%


次はハードロック曲。『HYDE:DOLLY』
元ファイル:20.7MB(=20660524byte)
エンコードファイル:21.7MB(21737495byte)

圧縮比:105.2%

あれれ。
とまぁこんな感じ。kの値を変更すれは改善の余地はあるはずです。
次回はmbed上に実装してみます。