圧縮とかtiny codec(Range Coder編)

RangeCoder(桁上がり無し版)を少ない文字数で実装しようという魂胆丸見えの企画です。終了判定は記号256で行います。

頻度表上限検査無

関数fが圧縮と展開を担います。Aは数値配列(要素は0～255)、dがfalsyな値なら圧縮処理、さもなければ展開処理。返り値は数値配列(要素は0～255)。変数B、L、RがRange Coderの役割を果たす。
沢山処理すると不具合出るきゃも?

f=(A,d)=>{
	var a=0,b,c,f,i,o=-4*!d,t=256,O=[],F=[],B,L=F[t]=0,R=1;
	for(F.fill(1);i^256;R*=f){
		// normalize
		for(;L>>>24==R+L>>>24||R<=65535&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
		R=R/++t>>>0;
		if(i=c=0,d){//decode
			for(b=(B-L>>>0)/R>>>0;f=F[i],f+c<=b;c+=f)i++;
			if(i^256)O[o++]=i
		}else{//encode
			for(b=A[a++]??256;f=F[i],b^i;c+=f)i++}
		F[i]++;L+=R*c
	}
	//final output
	for(;L;R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
	return O
}

removed dead code + minify 360bytes

f=(A,d)=>{var a=0,b,c,f,i,o=-4*!d,t=256,O=[],F=[],B,L=F[t]=0,R=1;for(F.fill(1);i^256;R*=f){for(i=c=-1;!((L^R+L)>>>24)||R<65536&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;R=R/++t>>>0;if(d){for(b=(B-L>>>0)/R>>>0;f=F[++i],f+c<b;)c+=f;if(i^256)O[o++]=i}else for(b=A[a++]??256;f=F[++i],b^i;)c+=f;F[i]++;L-=R*~c}for(;!d&&L;L<<=8)O[o++]=L>>>24;return O}

compressed + base64(復号後349bytes)

Zm9yKGY9J0ZbaV0TZm9yKBJ7EmI9ETtSKj0QPVtdLA87aWYoaQ4rKwxBW2EMXQs9MCwJT1tvDF09CD02NTUzNSYHPj4+BkwGMjQFO2Y9EywEO2MrPWYpaQwDMjU2AhACKWQ/Qj1CPDw4fAs6CAUsTDw8PTg7AWY9KEEsZCk9Pnt2YXIgYQliLGMsZixpLG89LTQqIWQsdD0CLE8PRg9CLEw9Rlt0XQlSPTE7EkYuZmlsbCgxKTtpXgIQZil7EjsFPT1SKwV8fFI8ByYoUgctTCkBUj1SLwx0BjAOPWMJZCkRKEItTAYwKS9SBjAEZitjPD1iAw5eAikIaX1lbHNlEQs/PwIEYl5pA30TDDtMKz1SKmN9EjtMAXJldHVybiBPfSc7Xz0vWwEtE10vLmV4ZWMoZik7KXdpdGgoZi5zcGxpdChfKSlmPWpvaW4oc2hpZnQoKSk7ZXZhbChmKQ

test

let src=[0,1,11,111,255],
enc=f(src), dec=f(enc,1);

頻度表上限検査有

頻度合計が8192以上なら全頻度半減する。使い方は前述同様

f=(A,d)=>{
	var a=0,b,c,f,i,o=-4*!d,t=256,O=[],F=[],B,L=F[t++]=0,R=1;
	for(F.fill(1);i^256;R*=f){
		for(;L>>>24==R+L>>>24||R<=65535&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
		R=R/t++>>>0;
		if(i=c=0,d){
			for(b=(B-L>>>0)/R>>>0;f=F[i],f+c<=b;c+=f)i++;
			if(i^256)O[o++]=i
		}else{for(b=A[a++]??256;f=F[i],b^i;c+=f)i++}
		L+=R*c;++F[i];
		//半減処理
		if(t>>>12)for(t=0,c=256;c--;)t+=F[c]-=F[c]>>>1
	}
	for(;L;R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
	return O
}

compressed + base64(復号後381bytes)

Zm9yKGY9J2ZvcigTexNiPRI7Uio9ET1bXSwQKysPQVthD10OPUZbDDtmDGldLAtPW28PXT0JPTY1NTM1Jgg7aWYoBz4+PgZMBjI0BT0wLAQ7Yys9ZilpDwMyNTYCEQIpZD9CPUI8PDh8DjoJBSxMPDw9ODsBZj0oQSxkKT0+e3ZhciBhBGIsYyxmLGksbz0tNCohZCx0PQIsTxBGEEIsTAx0D10EUj0xOxNGLmZpbGwoMSk7aV4CEWYpexM7BT09UisFfHxSPAgmKFIILUwpAVI9Ui90DwYwB2k9YwRkKRIoQi1MBjApL1IGMAtmK2M8PWIDB2leAikJaX1lbHNlEg4/PwILYl5pA31MKz1SKmM7D0ZbaV0HdAYxMikTdARjPQI7Yy0tOyl0KwxjXS0MY10GMX0TO0wBcmV0dXJuIE99JztfPS9bAS0TXS8uZXhlYyhmKTspd2l0aChmLnNwbGl0KF8pKWY9am9pbihzaGlmdCgpKTtldmFsKGYp

頻度更新+4ずつ、頻度表上限検査有

圧縮率良くなるかも

f=(A,d)=>{
	var a=0,b,c,f,i,o=-4*!d,t=256,O=[],F=[],B,L=F[t++]=0,R=1;
	for(F.fill(1);i^256;R*=f){
		for(;L>>>24==R+L>>>24||R<=65535&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
		R=R/t>>>0;
		if(i=c=0,d){
			for(b=(B-L>>>0)/R>>>0;f=F[i],f+c<=b;c+=f)i++;
			if(i^256)O[o++]=i
		}else{for(b=A[a++]??256;f=F[i],b^i;c+=f)i++}
		L+=R*c;F[i]+=4;t+=4;
		if(t>>>12)for(t=0,c=256;c--;)t+=F[c]-=F[c]>>>1
	}
	for(;L;R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
	return O
}

compressed + base64(復号後385bytes)

Zm9yKGY9J2ZvcigUexRiPRMrK10SQVthEhE7Uio9ED1bXSwPKz0OT1tvEj0MPUZbCztmC2ldLAk9NjU1MzUmCDtpZigHPj4+BkwGMjQFPTAsBDtjDmYpaSsrAzI1NgIQAilkP0I9Qjw8OHwROgwFLEw8PD04OwFmPShBLGQpPT57dmFyIGEEYixjLGYsaSxvPS00KiFkLHQ9AixPD0YPQixMC3QSBFI9MTsURi5maWxsKDEpO2leAhBmKXsUOwU9PVIrBXx8UjwIJihSCC1MKQFSPVIvdAYwB2k9YwRkKRMoQi1MBjApL1IGMAlmK2M8PWIDB2leAikMaX1lbHNlExE/PwIJYl5pA31MDlIqYztGW2ldDjQ7dA40B3QGMTIpFHQEYz0CO2MtLTspdCsLY10tC2NdBjF9FDtMAXJldHVybiBPfSc7Xz0vWwEtFF0vLmV4ZWMoZik7KXdpdGgoZi5zcGxpdChfKSlmPWpvaW4oc2hpZnQoKSk7ZXZhbChmKQ

order1、頻度更新+16ずつ

やや実用的な性能

f=(A,d)=>{
	for(var a=0,b,c,f=256,n=0,o=-4*!d,i=f++,O=[],F,T=[],B,L=0,R=1;i;F.t=f)F=T[--i]=Array(f).fill(1);
	for(;n^256;R*=f){
		for(F=T[n];L>>>24==R+L>>>24||R<=65535&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
		R=R/F.t>>>0;
		if(i=c=0,d){
			for(b=(B-L>>>0)/R>>>0;f=F[i],f+c<=b;c+=f)i++;
			if(i^256)O[o++]=i
		}else{for(b=A[a++]??256;f=F[i],b^i;c+=f)i++}
		L+=R*c;F[n=i]+=16;c=F.t+=16;
		if(c>>>12)for(F.t=1,i=256;i--;)F.t+=F[i]-=F[i]>>>1
	}
	for(;L;R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
	return O
}

compressed + base64(復号後423bytes)

Zm9yKGY9JysrFis9MTYVPUZbaV0UO2YULBNmb3IoEnsSYj0RRj1UWxA9W10sDz1mKQ5BW2EWXQw9MCwLO2lmKAk+Pj4ITAgyNAdPW28WXT0GPTY1NTM1JgVGLnQEO2MrDmkWAzI1NgI7Uio9AilkP0I9Qjw8OHwMOgYHLEw8PD04OwFmPShBLGQpPT57EnZhciBhC2IsYyxmPQIsbgtvPS00KiFkLGk9ZhYsTw9GLFQPQixMC1I9MTtpOwQOEC0taV09QXJyYXkoZikuZmlsbCgxKTsSO25eAjtSKg57EhBuXTsHPT1SKwd8fFI8BSYoUgUtTCkBUj1SLwQIMAlpPWMLZCkRKEItTAgwKS9SCDATZitjPD1iAwlpXgIpBml9ZWxzZREMPz8CE2JeaQN9TCs9UipjO0Zbbj1pXRU7Yz0EFQljCDEyKRIEPTEsaT0CO2ktLTspBCsULRQIMX0SO0wBcmV0dXJuIE99JztfPS9bAS0WXS8uZXhlYyhmKTspd2l0aChmLnNwbGl0KF8pKWY9am9pbihzaGlmdCgpKTtldmFsKGYp

order1,頻度更新 sum/16ずつ

若干実用的な性能

f=(A,d)=>{
	for(var a=0,b,c,f=256,n=0,o=-4*!d,i=f++,O=[],F,T=[],B,L=0,R=1;i;F.t=f)F=T[--i]=Array(f).fill(1);
	for(;n^256;R*=f){
		for(F=T[n];L>>>24==R+L>>>24||R<=65535&&(R=65535&-L);R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
		n=F.t;R=R/n>>>0;
		if(i=c=0,d){
			for(b=(B-L>>>0)/R>>>0;f=F[i],f+c<=b;c+=f)i++;
			if(i^256)O[o++]=i
		}else{for(b=A[a++]??256;f=F[i],b^i;c+=f)i++}
		L+=R*c;c=F.t+=n>>4;F[i]+=n>>4;n=i;
		if(c>>>13)for(F.t=1,i=256;i--;)F.t+=F[i]-=F[i]>>>1
	}
	for(;L;R*=256)d?B=B<<8|A[a++]:O[o++]=L>>>24,L<<=8;
	return O
}

compressed + base64(復号後429bytes)

Zm9yKGY9JysrF0ZbaV0WPRYVO2YVLBRmb3IoE3sTYj0SRj1UWxE9W10sED1mKQ9BW2EXXQ49MCwMO2lmKAs+Pj4JTAkyNAgrPW4+PjQ7B09bbxddPQY9NjU1MzUmBUYudAQ7YysPaRcDMjU2AjtSKj0CKWQ/Qj1CPDw4fA46BggsTDw8PTg7AWY9KEEsZCk9PnsTdmFyIGEMYixjLGY9AixuDG89LTQqIWQsaT1mFyxPEEYsVBBCLEwMUj0xO2k7BA8RLS1pXT1BcnJheShmKS5maWxsKDEpOxM7bl4CO1IqD3sTEW5dOwg9PVIrCHx8UjwFJihSBS1MKQFuPQQ7Uj1SL24JMAtpPWMMZCkSKEItTAkwKS9SCTAUZitjPD1iAwtpXgIpBml9ZWxzZRIOPz8CFGJeaQN9TCs9UipjO2M9BAcWB249aQtjCTEzKRMEPTEsaT0CO2ktLTspBCsVLRUJMX0TO0wBcmV0dXJuIE99JztfPS9bAS0XXS8uZXhlYyhmKTspd2l0aChmLnNwbGl0KF8pKWY9am9pbihzaGlmdCgpKTtldmFsKGYp