Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

arithmetic-coding

Package Overview
Dependencies
Maintainers
1
Versions
6
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

arithmetic-coding - npm Package Compare versions

Comparing version 1.1.0 to 1.2.0

test/file-info.js
test/test.js
test/txt/sample5.ref

0

.eslintrc.js

@@ -0,0 +0,0 @@ module.exports = {

0

bin/index.js

@@ -0,0 +0,0 @@ #!/usr/bin/env node

8

CHANGELOG.md

@@ -13,2 +13,8 @@ # arithmetic-coding CHANGELOG

- Added Buffer support.
- Added Buffer support.
## v1.2.0
2019.03.30
- Remove `long.js` and change number of bits for better performance.

5

package.json
{
"name": "arithmetic-coding",
"version": "1.1.0",
"version": "1.2.0",
"description": "Arithmetic coding implementation",

@@ -10,3 +10,3 @@ "main": "src/index.js",

"scripts": {
"test": "mocha --timeout 10000 && npm run clean",
"test": "mocha --timeout 100000 && npm run clean",
"clean": "rm test/txt/*-encoded.txt test/txt/*-decoded.txt",

@@ -39,3 +39,2 @@ "cover": "istanbul cover ./node_modules/mocha/bin/_mocha",

"concat-stream": "^2.0.0",
"long": "^4.0.0",
"which": "^1.3.1"

@@ -42,0 +41,0 @@ },

11

README.md

@@ -63,2 +63,13 @@ # arithmetic-coding

## Performance
You can see the latest [travis test](https://travis-ci.com/upupming/arithmetic-coding) for running time used by each test.
Some benchmarks are shown below:
| File size (Bytes) | total time used | encode time | decode time |
| ----------------- | --------------- | ----------- | ----------- |
| 60640 | 110ms | small | 110ms |
| 2130640 | 7419ms | | |
## About the algorithm

@@ -65,0 +76,0 @@

89

src/arithmetic-decoder.js

@@ -1,2 +0,1 @@

const Long = require('long');
const assert = require('assert');

@@ -28,10 +27,10 @@

// Maximum range (high+1-low) during coding (trivial), which is 2^num_state_bits = 1000...000.
this._full_range = new Long(1, 0).shiftLeft(numbits);
this._full_range = 1 << numbits >>> 0;
// console.log(`this._full_range: ${this._full_range.toString(16)}`);
// The top bit at width num_state_bits, which is 0100...000.
this._half_range = this._full_range.shiftRightUnsigned(1); // Non-zero
this._half_range = this._full_range >>> 1;
// The second highest bit at width num_state_bits, which is 0010...000. This is zero when num_state_bits=1.
this._quarter_range = this._half_range.shiftRightUnsigned(1); // Can be zero
this._quarter_range = this._half_range >>> 1; // Can be zero
// Minimum range (high+1-low) during coding (non-trivial), which is 0010...010.
this._minimum_range = this._quarter_range.add(2); // At least 2
this._minimum_range = this._quarter_range + 2; // At least 2
// Maximum allowed total from a frequency table at all times during coding. This differs from Java

@@ -42,3 +41,3 @@ // and C++ because Python's native bigint avoids constraining the size of intermediate computations.

// Bit mask of num_state_bits ones, which is 0111...111.
this._state_mask = this._full_range.sub(1);
this._state_mask = this._full_range - 1;
// console.log(`this._state_mask: ${this._state_mask.toString(16)}`);

@@ -48,3 +47,3 @@

// Low end of this arithmetic coder's current range. Conceptually has an infinite number of trailing 0s.
this._low = new Long(0, 0);
this._low = 0;
// console.log(`this._low: ${this._low.toString(16)}`);

@@ -59,5 +58,5 @@ // High end of this arithmetic coder's current range. Conceptually has an infinite number of trailing 1s.

// The current raw code bits being buffered, which is always in the range [low, high].
this._code = new Long(0, 0);
this._code = 0;
for (let i = 0; i < this._num_state_bits; i++) {
this._code = this._code.shiftLeft(1).or(this.readCodeBit());
this._code = (this._code << 1) | this.readCodeBit();
// console.log(`this._code_init = ${this._code}`);

@@ -76,13 +75,15 @@ }

let total = freqs.total;
if (this._maximum_total.lessThan(total)) {
if (this._maximum_total >>> 0 < total >>> 0) {
throw RangeError('Cannot decode symbol because total is too large');
}
let range = this._high.sub(this._low).add(1);
let offset = this._code.sub(this._low);
let value = offset.add(1).mul(total).sub(1).div(range);
let range = ((this._high - this._low) + 1) >>> 0;
let offset = this._code - this._low;
let value = Math.floor((((offset + 1) * total) - 1) / range);
// console.log(`this._code_cal = ${this._code}, offset = ${offset}, value = ${value}`);
assert(value.mul(range).div(total).lessThanOrEqual(offset));
assert(Math.floor((value * range) / total) >>> 0 <= offset >>> 0);
// console.log(`range = ${range.toString(16)}`);
// console.log(`offset = ${offset.toString(16)}`);
// console.log(`value = ${value.toString(16)}`);
// console.log(`total = ${total.toString(16)}`);
assert(value.greaterThanOrEqual(0) && value.lessThan(total));
// console.log(`total = ${total.toString(16)}, ${typeof total}`);
assert((value >>> 0 >= 0) && (value >>> 0 < total >>> 0));

@@ -97,3 +98,3 @@ // A kind of binary search.

// console.log(`freqs.getLow(middle) = ${freqs.getLow(middle)}`);
if (value.lessThan(freqs.getLow(middle))) {
if (value >>> 0 < freqs.getLow(middle)) {
end = middle;

@@ -110,7 +111,7 @@ } else {

assert(
range.mul(freqs.getLow(symbol)).div(total).lessThanOrEqual(offset) &&
offset.lessThan(range.mul(freqs.getHigh(symbol)).div(total))
(Math.floor((range * (freqs.getLow(symbol))) / (total)) >>> 0 <= offset >>> 0) &&
offset >>> 0 <= Math.floor(range * (freqs.getHigh(symbol)) / (total)) >>> 0
);
this.update(freqs, symbol);
if (!(this._low.lessThanOrEqual(this._code) && this._code.lessThanOrEqual(this._high))) {
if (!(this._low >>> 0 <= this._code >>> 0 && this._code >>> 0 <= this._high >>> 0)) {
throw new RangeError('Code out of range');

@@ -151,8 +152,12 @@ }

// console.log(`======== Updating ${symbol} =========`);
// console.log(`this._low = ${this._low.toString(16)}`, `this._high = ${this._high.toString(16)}`);
if (low.greaterThanOrEqual(high) || low.and(this._state_mask).notEquals(low) || high.and(this._state_mask).notEquals(high)) {
throw RangeError('Low or high out of range');
// console.log(`this._low = ${this._low.toString(16)}`);
// console.log(`this._high = ${this._high.toString(16)}`);
// console.log(`low & this._state_mask = ${low & this._state_mask.toString(16)}`);
// console.log(`high & (this._state_mask) = ${high & (this._state_mask).toString(16)}`);
if (low >>> 0 >= high >>> 0 || ((low & this._state_mask) !== low) || ((high & (this._state_mask)) !== high)) {
throw RangeError(`Low or high out of range, low = ${low}, high = ${high}`);
}
let range = high.sub(low).add(1);
if (!(this._minimum_range.lessThanOrEqual(range) && range.lessThanOrEqual(this._full_range))) {
let range = high - low + 1;
// console.log(`range = ${range.toString(16)}`);
if (!(this._minimum_range >>> 0 <= range >>> 0 && range >>> 0 <= this._full_range >>> 0)) {
throw RangeError('Range out of range');

@@ -165,8 +170,8 @@ }

let symhigh = freqs.getHigh(symbol);
// console.log(`symlow = ${symlow.toString(16)}`, `symhigh = ${symhigh.toString(16)}`);
// console.log(`total = ${total}`);
// console.log(`symlow = ${symlow.toString(16)}`);
// console.log(`symhigh = ${symhigh.toString(16)}`);
if (symlow === symhigh) {
throw Error('Symbol has zero frequency');
}
if (this._maximum_total.lessThan(total)) {
if (this._maximum_total >>> 0 <= total >>> 0) {
throw Error('Cannot code symbol because total is too large');

@@ -176,13 +181,15 @@ }

// Update
let newlow = low.add(range.mul(symlow).div(total));
let newhigh = low.add(range.mul(symhigh).div(total)).sub(1);
// console.log(`total = ${total.toString(16)}`);
let newlow = low + Math.floor(range * symlow / total);
let newhigh = low + Math.floor(range * symhigh / total) - 1;
// console.log(`newlow = ${newlow.toString(16)}`);
// console.log(`newhigh = ${newhigh.toString(16)}`);
this._low = newlow;
this._high = newhigh;
// console.log(`newlow = ${newlow.toString(16)}`, `newhigh = ${newhigh.toString(16)}`);
// While low and high have the same top bit value, shift them out
while (((this._low.xor(this._high)).and(this._half_range)).equals(0)) {
while (((this._low ^ this._high) & (this._half_range)) === 0) {
this._shift();
this._low = this._low.shiftLeft(1).and(this._state_mask);
this._high = this._high.shiftLeft(1).and(this._state_mask).or(1);
this._low = (this._low << 1) & (this._state_mask);
this._high = (this._high << 1) & (this._state_mask) | 1;
}

@@ -193,6 +200,6 @@

// While low's top two bits are 01 and high's are 10, delete the second highest bit of both
while ((this._low.and(this._high.not()).and(this._quarter_range)).notEquals(0)) {
while ((this._low & (~this._high) & (this._quarter_range)) !== 0) {
this._underflow();
this._low = this._low.shiftLeft(1).xor(this._half_range);
this._high = this._high.xor(this._half_range).shiftLeft(1).or(this._half_range).or(1);
this._low = (this._low << 1) ^ (this._half_range);
this._high = ((this._high ^ (this._half_range)) << 1) | this._half_range | 1;
}

@@ -202,9 +209,9 @@ }

_shift() {
this._code = this._code.shiftLeft(1).and(this._state_mask).or(this.readCodeBit());
this._code = (this._code << 1) & (this._state_mask) | (this.readCodeBit());
// console.log(`this._code_shift = ${this._code}`);
}
_underflow() {
this._code = this._code.and(this._half_range).or(
this._code.shiftLeft(1).and(this._state_mask.shiftRightUnsigned(1))
).or(this.readCodeBit());
this._code = this._code & (this._half_range) | (
this._code << 1 & (this._state_mask >>> 1)
) | (this.readCodeBit());
// console.log(`this._code_underflow = ${this._code}`);

@@ -211,0 +218,0 @@ }

52

src/arithmetic-encoder.js

@@ -1,3 +0,1 @@

var Long = require('long');
module.exports = class ArithmeticEncoder {

@@ -27,10 +25,10 @@ /**

// Maximum range (high+1-low) during coding (trivial), which is 2^num_state_bits = 1000...000.
this._full_range = new Long(1, 0).shiftLeft(numbits);
this._full_range = (1 << numbits) >>> 0;
// console.log(`this._full_range: ${this._full_range.toString(16)}`);
// The top bit at width num_state_bits, which is 0100...000.
this._half_range = this._full_range.shiftRightUnsigned(1); // Non-zero
this._half_range = this._full_range >>> 1; // Non-zero
// The second highest bit at width num_state_bits, which is 0010...000. This is zero when num_state_bits=1.
this._quarter_range = this._half_range.shiftRightUnsigned(1); // Can be zero
this._quarter_range = this._half_range >>> 1; // Can be zero
// Minimum range (high+1-low) during coding (non-trivial), which is 0010...010.
this._minimum_range = this._quarter_range.add(2); // At least 2
this._minimum_range = this._quarter_range + 2; // At least 2
// Maximum allowed total from a frequency table at all times during coding. This differs from Java

@@ -41,3 +39,3 @@ // and C++ because Python's native bigint avoids constraining the size of intermediate computations.

// Bit mask of num_state_bits ones, which is 0111...111.
this._state_mask = this._full_range.sub(1);
this._state_mask = this._full_range - 1;
// console.log(`this._state_mask: ${this._state_mask.toString(16)}`);

@@ -47,3 +45,3 @@

// Low end of this arithmetic coder's current range. Conceptually has an infinite number of trailing 0s.
this._low = new Long(0, 0);
this._low = 0;
// console.log(`this._low: ${this._low.toString(16)}`);

@@ -81,10 +79,10 @@ // High end of this arithmetic coder's current range. Conceptually has an infinite number of trailing 1s.

// console.log(`this._high = ${this._high.toString(16)}`);
// console.log(`low.and(this._state_mask) = ${low.and(this._state_mask).toString(16)}`);
// console.log(`high.and(this._state_mask) = ${high.and(this._state_mask).toString(16)}`);
if (low.greaterThanOrEqual(high) || low.and(this._state_mask).notEquals(low) || high.and(this._state_mask).notEquals(high)) {
throw RangeError('Low or high out of range');
// console.log(`low & this._state_mask = ${low & this._state_mask.toString(16)}`);
// console.log(`high & (this._state_mask) = ${high & (this._state_mask).toString(16)}`);
if (low >>> 0 >= high >>> 0 || ((low & this._state_mask) !== low) || ((high & (this._state_mask)) !== high)) {
throw RangeError(`Low or high out of range, low = ${low}, high = ${high}`);
}
let range = high.sub(low).add(1);
let range = high - low + 1;
// console.log(`range = ${range.toString(16)}`);
if (!(this._minimum_range.lessThanOrEqual(range) && range.lessThanOrEqual(this._full_range))) {
if (!(this._minimum_range >>> 0 <= range >>> 0 && range >>> 0 <= this._full_range >>> 0)) {
throw RangeError('Range out of range');

@@ -102,3 +100,3 @@ }

}
if (this._maximum_total.lessThan(total)) {
if (this._maximum_total >>> 0 <= total >>> 0) {
throw Error('Cannot code symbol because total is too large');

@@ -109,4 +107,4 @@ }

// console.log(`total = ${total.toString(16)}`);
let newlow = low.add(range.mul(symlow).div(total));
let newhigh = low.add(range.mul(symhigh).div(total)).sub(1); // total - 1
let newlow = low + Math.floor(range * symlow / total);
let newhigh = low + Math.floor(range * symhigh / total) - 1;
// console.log(`newlow = ${newlow.toString(16)}`);

@@ -118,6 +116,6 @@ // console.log(`newhigh = ${newhigh.toString(16)}`);

// While low and high have the same top bit value, shift them out
while (((this._low.xor(this._high)).and(this._half_range)).equals(0)) {
while (((this._low ^ this._high) & (this._half_range)) === 0) {
this._shift();
this._low = this._low.shiftLeft(1).and(this._state_mask);
this._high = this._high.shiftLeft(1).and(this._state_mask).or(1);
this._low = (this._low << 1) & (this._state_mask);
this._high = (this._high << 1) & (this._state_mask) | 1;
}

@@ -128,6 +126,6 @@

// While low's top two bits are 01 and high's are 10, delete the second highest bit of both
while ((this._low.and(this._high.not()).and(this._quarter_range)).notEquals(0)) {
while ((this._low & (~this._high) & (this._quarter_range)) !== 0) {
this._underflow();
this._low = this._low.shiftLeft(1).xor(this._half_range);
this._high = this._high.xor(this._half_range).shiftLeft(1).or(this._half_range).or(1);
this._low = (this._low << 1) ^ (this._half_range);
this._high = ((this._high ^ (this._half_range)) << 1) | this._half_range | 1;
}

@@ -156,10 +154,10 @@ }

_shift() {
let bit = this._low.shiftRightUnsigned(this._num_state_bits - 1);
let bit = this._low >>> (this._num_state_bits - 1);
// console.log(`bit = ${bit}`);
this._output.write(bit.toNumber());
this._output.write(bit);
// Write out the saved underflow bits
for (let i = 0; i < this._num_underflow; i++) {
// console.log(`bit.xor(1) = ${bit.xor(1)}`);
this._output.write(bit.xor(1).toNumber());
// console.log(`bit ^ 1 = ${bit ^ 1}`);
this._output.write(bit ^ 1);
}

@@ -166,0 +164,0 @@ this._num_underflow = 0;

2

src/bit-input-stream.js

@@ -50,3 +50,3 @@ const fs = require('fs');

let numOfBytesRead = fs.readSync(this._input, temp, 0, CACHE_SIZE, null);
this._cachedBytes = Buffer.concat([this._cachedBytes, temp], numOfBytesRead);
this._cachedBytes = temp.slice(0, numOfBytesRead);
if (numOfBytesRead < CACHE_SIZE) {

@@ -53,0 +53,0 @@ this._streamEnded = true;

6

src/bit-output-stream-buffer.js

@@ -10,3 +10,3 @@ /**

// The underlying file stream to write to
this._buffer = Buffer.alloc(0);
this._bytes = [];
// The accumulated bits for the current byte,

@@ -30,3 +30,3 @@ // always in range [0x00, 0xFF]

if (this._numbitsfilled === 8) {
this._buffer = Buffer.concat([this._buffer, Buffer.from([this._currentbyte])]);
this._bytes.push(this._currentbyte);
this._currentbyte = 0;

@@ -42,4 +42,4 @@ this._numbitsfilled = 0;

get buffer() {
return this._buffer;
return Buffer.from(this._bytes);
}
};

6

src/bit-output-stream.js

@@ -16,2 +16,3 @@ const fs = require('fs');

this._output = fs.openSync(outputfile, 'w');
this._bytes = [];
// The accumulated bits for the current byte,

@@ -35,5 +36,3 @@ // always in range [0x00, 0xFF]

if (this._numbitsfilled === 8) {
let towrite = Buffer.from([this._currentbyte]);
// this._output.writeSync(towrite);
fs.writeSync(this._output, towrite, 0, 1, null);
this._bytes.push(this._currentbyte);
this._currentbyte = 0;

@@ -47,4 +46,5 @@ this._numbitsfilled = 0;

}
fs.writeSync(this._output, Buffer.from(this._bytes), 0, this._bytes.length, null);
fs.closeSync(this._output);
}
};

21

src/decode.js

@@ -5,5 +5,6 @@ const fs = require('fs');

const BitInputStreamFromBuffer = require('./bit-input-stream-buffer');
const Long = require('long');
const ArithmeticDecoder = require('./arithmetic-decoder');
const NUM_OF_BITS = 31;
/**

@@ -38,7 +39,7 @@ * Decode a file using arithmetic coding algorithm

function readInt(n) {
let result = new Long(0, 0);
let result = 0;
for (let i = 0; i < n; i++) {
let tmp = bitin.readNoEOF();
// console.log(tmp);
result = result.shiftLeft(1).or(tmp); // Big endian
result = result << 1 | tmp; // Big endian
}

@@ -50,3 +51,3 @@ return result;

for (let i = 0; i < 256; i++) {
freqs[i] = readInt(32).toNumber();
freqs[i] = readInt(NUM_OF_BITS);
// console.log(`freqs[${i}] = `, freqs[i]);

@@ -64,3 +65,4 @@ // acc += freqs[i];

let output = fs.openSync(outputfile, 'w');
const dec = new ArithmeticDecoder(32, bitin);
let bytes = [];
const dec = new ArithmeticDecoder(NUM_OF_BITS, bitin);
for (;;) {

@@ -75,4 +77,5 @@ let symbol = dec.read(freqs);

// output.wr();
fs.writeSync(output, Buffer.from([symbol]), 0, 1, null);
bytes.push(symbol);
}
fs.writeSync(output, Buffer.from(bytes), 0, bytes.length, null);
fs.closeSync(output);

@@ -88,3 +91,4 @@ }

let buffer = Buffer.alloc(0);
const dec = new ArithmeticDecoder(32, bitin);
let bytes = [];
const dec = new ArithmeticDecoder(NUM_OF_BITS, bitin);
for (;;) {

@@ -98,4 +102,5 @@ let symbol = dec.read(freqs);

// console.log(`writing ${symbol}`);
buffer = Buffer.concat([buffer, Buffer.from([symbol])]);
bytes.push(symbol);
}
buffer = Buffer.from(bytes);
return buffer;

@@ -102,0 +107,0 @@ }

7

src/encode.js

@@ -8,2 +8,3 @@ const fs = require('fs');

const CACHE_SIZE = 20000;
const NUM_OF_BITS = 31;

@@ -93,3 +94,3 @@ /**

// console.log(freqs);
write_int(bitout, 32, freqs.get(i));
write_int(bitout, NUM_OF_BITS, freqs.get(i));
}

@@ -118,3 +119,3 @@ }

function compress(freqs, inputfile, bitout) {
let enc = new ArithmeticEncoder(32, bitout);
let enc = new ArithmeticEncoder(NUM_OF_BITS, bitout);
let input = fs.openSync(inputfile, 'r');

@@ -146,3 +147,3 @@ for(;;) {

function compressFromBuffer(freqs, inBuffer, bitout) {
let enc = new ArithmeticEncoder(32, bitout);
let enc = new ArithmeticEncoder(NUM_OF_BITS, bitout);
for (let byte of inBuffer) {

@@ -149,0 +150,0 @@ enc.write(freqs, byte);

5

test/1_encode.test.js
require('should');
const encode = require('../src/encode');
const fileInfo = require('./file-info');
describe('encode', function() {
describe('getFrequencies', function() {
describe('getFrequencies ' + fileInfo(__dirname + '/txt/short.txt'), function() {
it('should construct frequency table', function() {

@@ -19,3 +20,3 @@ let freqs = encode.getFrequencies(__dirname + '/txt/short.txt');

});
describe('encode', function() {
describe('encode ' + fileInfo(__dirname + '/txt/short.txt'), function() {
it('should encode okay', function() {

@@ -22,0 +23,0 @@ encode.encode(__dirname + '/txt/short.txt', __dirname + '/txt/short-encoded.txt');

3

test/2_decode.test.js
var fs = require('fs');
require('should');
const decode = require('../src/decode');
const fileInfo = require('./file-info');
describe('decode', function () {
it('should decode okay', function () {
it('should decode okay ' + fileInfo(__dirname + '/txt/short.txt'), function () {
decode.decode(__dirname + '/txt/short-encoded.txt', __dirname + '/txt/short-decoded.txt');

@@ -8,0 +9,0 @@ });

3

test/3_index.test.js
require('should');
const ariCoding = require('../src/index');
var fs = require('fs');
const fileInfo = require('./file-info');
describe('Package test', function() {
describe('encode & decode', function() {
describe('encode & decode ' + fileInfo(__dirname + '/txt/long.txt'), function() {
it('should encode', function() {

@@ -8,0 +9,0 @@ ariCoding.encode(__dirname + '/txt/long.txt', __dirname + '/txt/long-encoded.txt');

3

test/4_cli.test.js

@@ -5,4 +5,5 @@ const cmd = require('./cmd');

const fs = require('fs');
const fileInfo = require('./file-info');
describe('CLI test', () => {
describe('CLI test ' + fileInfo(__dirname + '/txt/long.txt'), () => {
it('should print help if input is invalid', async () => {

@@ -9,0 +10,0 @@ try {

8

test/5_buffer-support.test.js
require('should');
const encode = require('../src/encode');
const decode = require('../src/decode');
const fs = require('fs');
const fileInfo = require('./file-info');
const filepath = __dirname + '/txt/sample5.ref';
describe('Buffer support', function () {
it('should encode and decode Buffer okay', function() {
let data = Buffer.from('Example data', 'utf8');
it('should encode and decode Buffer okay ' + fileInfo(filepath), function() {
let data = fs.readFileSync(filepath);
let encoded = encode.encodeFromBuffer(data);

@@ -9,0 +13,0 @@ // console.log(`encoded = ${encoded}`);

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc