Onda lossless audio compression algorithm  &
Onda file formats

Table of contents

You must have JavaScript enabled in your browser to generate the table of contents.

1  Onda lossless audio compression algorithm

1.1  Overview

The Onda algorithm is very simple: it works by encoding the second difference of successive sample values from each audio channel. The first difference is the difference between successive sample values; the second difference is the difference between successive first differences — the discrete analogue of the second derivative. If St−2 , St−1 and St are three successive sample values, the second difference at t, ΔΔSt , is given by

ΔΔSt = ΔSt − ΔSt−1
= (St − St−1) − (St−1 − St−2)
St − 2St−1 + St−2 .

General-purpose compression algorithms such as Huffman encoding work poorly on sampled sound data because the data values are widely distributed. Compression of sound data usually involves some sort of prediction; in the case of the Onda algorithm, prediction is based on a crude model of a waveform in which the differences between successive sample values — and the differences between the differences — are expected to be significantly smaller than the values themselves. From tests with various genres of music, it was found that encoding the second difference generally resulted in greater compression than encoding the first difference, with only a small reduction in the efficiency of the algorithm.

The following terms are used in the remainder of this section:

block
A group of contiguous sample frames that is treated as an independent logical entity by the Onda algorithm. Input data are encoded in blocks of an arbitrary length.
block channel
The sequence of sample values that comprise a single audio channel within a block.
block length
The number of sample frames in a block. Block length is arbitrary and can vary throughout a file. The length of a block must be known before it can be encoded or decoded.
delta
A first difference: the difference between successive sample values from the same block channel.
encoding key
A representation of the encoding length that is used to encode a block channel.
encoding length
The length of the bit string that is used to encode an epsilon. It must be in the range [1 .. sampleLength − 1].
encoding limit
For a given encoding length, the maximum absolute value of an epsilon, 2encodingLength − 1 − 1 .
epsilon
A second difference: the difference between successive first differences (deltas) from the same block channel.
excess code
For a given encoding length, the value 2encodingLength − 1 (a bit string of all 1s), which is used as a prefix to an explicit sample value in place of an epsilon that exceeds the encoding limit.
excess count
For a given encoding length, the number of epsilons in a block channel whose absolute value exceeds the encoding limit.
sample frame
A synchronous group of sample values: one sample value for each audio channel of the input data at a point in time. For example, a sample frame from stereo (2-channel) input data at time t consists of a pair of sample values: the sample value for the left channel at t, and the sample value for the right channel at t.
sample length
The bit length of sample values in the input data, which is also the length of the bit string that is used by the Onda algorithm to encode explicit sample values. The term sample length is used in preference to alternative terms to emphasise the relationship to encoding length.

In broad terms, the Onda algorithm works by dividing the input data into blocks of arbitrary length, then encoding the second differences (epsilons) for each block channel with bit strings of the optimum length. The algorithm has two stages: optimisation and encoding. Although optimisation is performed before encoding, the encoding algorithm is described first so that the aim of optimisation may be more readily understood.

1.2  Encoding

The method by which a block of sample data is encoded with a specified encoding length is described in pseudocode by the ONDA-ENCODE algorithm below. It is a simplified description, applying only to sample data from a single audio channel, but it can be generalised to any number of channels since the Onda algorithm treats each audio channel independently.

The ONDA-ENCODE algorithm forms the essential (and prescriptive) part of the Onda compression algorithm. It assumes bit-oriented binary data and two's-complement signed integer arithmetic. The ONDA-COMPRESS algorithm, which is based on the ONDA-ENCODE algorithm, introduces implementation details that are not specified by the ONDA-ENCODE algorithm. (For instance, block channels are interleaved in the compressed data.)

A block channel is encoded in one of two ways depending on the encoding length:

  1. If the encoding length of a block channel is equal to the sample length, all the sample values for that channel are written to the output without modification (ie, each sample value is encoded as a bit string whose length is the sample length). The size of data encoded in this way is the size of the input data plus a few extra bits for the encoding key, which means that the worst-case compression ratio for the Onda algorithm is around 100.1%.
  2. If the encoding length of a block channel is less than the sample length, the sample values for that channel are encoded in one of three ways:
    1. The first sample value of each block channel is always encoded without modification, as a bit string whose length is the sample length. This enables each block to be compressed or expanded independently from other blocks in a file, but at the cost of an output that is around 0.2% larger than it would be if the first sample value were encoded as a continuation of the previous block.
    2. Apart from the first sample in the block, a sample value is encoded as an epsilon if the absolute value of the epsilon is less than or equal to the encoding limit, 2encodingLength − 1 − 1. The length of an epsilon bit string is the encoding length.
    3. If a sample value cannot be encoded as an epsilon because the absolute value of the epsilon is greater than the encoding limit, the sample value is encoded as an excess code (a bit string of all 1s whose length is the encoding length) followed by the unmodified sample value (a bit string whose length is the sample length). The excess code for a given encoding length is not a valid epsilon value; when it is encountered during decompression, it indicates that an explicit sample value follows.

Each encoded bit string, regardless of its length, is a two's-complement signed integer.

Algorithm: ONDA-ENCODE

Input: sampleLength, encodingLength, blockLength

Auxiliary operations:

Read( )
Reads and returns the next sample value from the input.
Write( valuelength )
Writes the length low-order bits of value to the output.

{--- Start of pseudocode ---}

{--- End of pseudocode ---}

Table 1.1 below shows the deltas, epsilons and output values from the encoding of four stereo sample frames of arbitrary sample values at the start of a block. The sample length is 16 bits and the encoding length is 13 bits, which gives an encoding limit of 4095. (The optimum encoding length for the input values is 14; a suboptimal encoding length was chosen to illustrate the use of excess codes. The suboptimal encoding length of 13 results in an output that is larger than the input.) The encoded data are shown in figure 1.1, with channels interleaved.

# Input value Delta Epsilon Output value [length]
0 L -2345 (0xF6D7) -2345 -2345 0xF6D7 [16]  
R -887 (0xFC89) -887 -887 0xFC89 [16]  
1 L 1284 (0x0504) 3629 5974 0x1000 [13] 0x0504 [16]
R 906 (0x038A) 1793 2680 0x0A78 [13]  
2 L 7331 (0x1CA3) 6047 2418 0x0972 [13]  
R 8425 (0x20E9) 7519 5726 0x1000 [13] 0x20E9 [16]
3 L 12236 (0x2FCC) 4905 -1142 0x1B8A [13]  
R 14170 (0x375A) 5745 -1774 0x1912 [13]  

Table 1.1

encoding

Figure 1.1

1.3  Optimisation

Optimisation of the encoding of a block channel entails determining, from an arbitrary set of valid encoding lengths, the encoding length that results in the smallest output; the optimum encoding length is then used to encode the block channel. An encoding length must be in the range [1 .. sampleLength − 1]. If the set of candidate encoding lengths for optimisation includes all valid encoding lengths for a given sample length, the encoding length is fully optimised.

The ONDA-COMPRESS algorithm determines the optimum encoding length from a range whose lower limit depends on the length of the encoding key, keyLength. The encoding lengths used by the algorithm are fully optimised if keyLength ≥ ⌊log2sampleLength − 1)⌋ .

The following procedure determines the optimum encoding length for a single block channel from a set of encoding lengths, L:

1.4  Compression

The ONDA-COMPRESS algorithm extends the ONDA-ENCODE algorithm to multiple audio channels and introduces some implementation details that are not specified by ONDA-ENCODE:

These details correspond to the implementation of the compression algorithm in the Onda application.

Algorithm: ONDA-COMPRESS

Input: numChannels, sampleLength, numSampleFrames, keyLength, blockLength

Auxiliary operations:

Read( )
Reads and returns the next sample frame from the input.
Write( valuelength )
Writes the length lowest bits of value to the output.

{--- Start of pseudocode ---}

{--- End of pseudocode ---}

1.5  Decompression

The ONDA-DECOMPRESS algorithm decompresses data that were encoded with the ONDA-COMPRESS algorithm. It makes the following assumptions, which correspond to implementation details introduced by ONDA-COMPRESS:

Algorithm: ONDA-DECOMPRESS

Input: numChannels, sampleLength, numSampleFrames, keyLength, blockLength

Auxiliary operations:

ReadSigned( length )
Reads length bits from the input, extends the assumed sign bit (the bit at index length − 1) to the higher-order bits, then returns the value as an signed integer.
ReadUnsigned( length )
Reads length bits from the input and returns the value as an unsigned integer.
Write( sampleFrame[ ] )
Writes the synchronous sample values in sampleFrame to the output.

{--- Start of pseudocode ---}

{--- End of pseudocode ---}

2  Old (IFF) ONDA file format

The Onda application has used two formats for its compressed audio files. The formats are referred to in this document as the old (or IFF) format and the new (or NLF) format. The old format was used for the compressed files that were written by the Onda application up to and including version 1.2. From version 1.3, compressed files are written in the new format. All versions of the Onda application can read the old file format, but the new format can be read by the application only from version 1.3 onwards.

2.1  ONDA FORM chunk

An ONDA file conforms to the Electronic Arts Interchange File Format (EA IFF 1985) standard. It consists of a single IFF FORM group chunk that contains two required chunks (attributes and data), and may contain two optional chunks (private data and data block size). The order of the chunks within the FORM group is specified in table 2.1.

Although the form of the chunks in a new Onda file is different from the form of the chunks in an old ONDA file, the content of the chunks in an ONDA FORM is the same as that of the chunks in the root list of the new Onda file format. For details of the chunks in the old format, refer to the relevant sections in the specification of the new format, substituting the IFF identifiers of the chunks in table 2.1 for those of the new format.

The amount of sample data that can be stored in an ONDA file is limited by the upper bound of the size of an IFF chunk (2 GiB). The data type of the size of chunks in the IFF and RIFF is a problematic subject that is discussed in Appendix A.

Note:  All integer values in an ONDA file are big-endian and unsigned.

ONDA FORM group
ID = ONDA
Multiplicity Description Identifier
1 Attributes chunk ATTR
0..1 Private data chunk PRVT
0..1 Data block size chunk DBSZ
1 Data chunk DATA

Table 2.1

3  New (NLF) Onda file format

The new Onda file format — the title-case "Onda", like the upper-case "ONDA" of the old format, comes from the identifier of the top-level container of the file — was introduced in version 1.3 of the Onda application to allow for larger compressed files. From version 1.3, the application can read files in both the old and new formats, but compressed files are written only in the new format.

The Onda application has been — and is likely to continue to be — of very little general interest, so the introduction of a new file format would seem to be a waste of effort. The development of a new format was motivated by a perceived need to replace the old Electronic Arts Interchange File Format (EA IFF 1985) with a general, chunk-based file format for binary data that could accommodate a larger chunk size. The result was the Nested-List File (NLF) format (also likely to be of minimal general interest), which has been published as an open format.

3.1  Onda list

An Onda file conforms to the Nested-List File format. Its root list (list-instance ID = "Onda") contains two required chunks (attributes and data), and may contain two optional chunks (private data and data block size). The order of the chunks within the list is specified in table 3.1.

The capacity of an Onda file is limited to about 262 bytes by the upper bound of an NLF chunk.

Note:  All integer values in an Onda file (ie, values in chunk headers and chunk content) are big-endian and unsigned.

Onda list
List-instance ID = Onda
Multiplicity Description Identifier
1 Attributes chunk attributes
0..1 Private data chunk privateData
0..1 Data block size chunk dataBlockSize
1 Data chunk data

Table 3.1

3.2  Attributes chunk (required)

An Onda file must contain one attributes chunk, whose identifier is "attributes". The first two bytes of the attributes chunk are the version number of the file format, from which the structure of the attributes chunk can be inferred.

Only versions 0 and 1 are currently defined; the structure of the attributes chunk is the same for both versions. Files of version 1 contain a private data chunk; files of version 0 do not.

The attributes chunk contains values that are required to expand the data in the data chunk, and to validate the expanded sample data. The entries in the Values column in table 3.2 are the ranges that are considered valid by the current Onda application, though it does not necessarily support all values in the range. (For example, it currently supports only 16 and 24 bits per sample.)

Note that the attributes chunk in an Onda file is a application-specific chunk, not the special attributes chunk (ID = "$ATTR") of a list in a Nested-List File. The unfortunate ambiguity in terminology is a legacy of the attributes chunk in the old ONDA file format.

Attributes chunk, version 0 or 1
ID = attributes
Multiplicity Name Description Values Size
1 version Version number 0..32767 2 bytes
1 numChannels Number of channels 1..128 2 bytes
1 bitsPerSample Number of bits per sample 1..32 2 bytes
1 sampleRate Sample rate, Hz 1..231−1 4 bytes
1 numSampleFrames Number of sample frames 0..262−1 8 bytes
1 crcValue 32-bit CRC value   4 bytes
1 keyLength Key length, bits 1..5 2 bytes
1 blockLength Block length, sample frames 1..65536 4 bytes
Total size 28 bytes

Table 3.2

3.3  Data chunk (required)

An Onda file must contain one data chunk, whose identifier is "data".

The number of data blocks (the value of n in table 3.3 and table 3.6) is given by

  n = ⌊(numSampleFrames + blockLength − 1) / blockLength⌋ .

The compressed sample data are stored in the data chunk as zero or more data blocks. The contents of the data chunk are bit-oriented; that is, the data (and data blocks) are of variable bit lengths and are not aligned on byte boundaries. A data block encodes a number of contiguous sample frames from a multi-channel audio source. A sample frame consists of the sample value for each audio channel at a point in time, with channels interleaved as in a WAVE or AIFF file. The number of sample frames in a data block is denoted by the blockLength attribute: in a file containing n data blocks, the first n − 1 blocks contain blockLength sample frames, and the last data block contains numSampleFrames − (n − 1) × blockLength sample frames.

Data chunk
ID = data
Multiplicity Description
n Compressed sample data blocks (see table 3.4)

Table 3.3

The bit-oriented data in a data block are in two parts: the first part comprises the compression keys for each audio channel; the second part comprises the compressed sample data, arranged as contiguous sample frames. While the length of the compression keys is known beforehand, the size of the compressed sample data (and thence the size of the data block) is variable and cannot be obtained without parsing the data, although full decompression is not necessary. Thus, the version of the Onda file format specified in this document does not allow random access to data blocks. The Onda compression algorithm, on the other hand, does allow random access to data blocks because the data blocks are independent of each other, so random access can be achieved by including a data block size chunk in the Onda file.

Data block
Multiplicity Description Size
numChannels Compression keys numChannels × keyLength bits
1 Compressed sample data, interleaved d bits

Table 3.4

3.4  Private data chunk (optional)

An Onda file may contain one private data chunk, whose identifier is "privateData".

A private data chunk contains private data from the original audio file that have been compressed with the DEFLATE algorithm. For an AIFF or WAVE file, private data refers to the content of ancillary chunks within the file.

The version field in the attributes chunk should be set to 1 if the file contains a private data chunk, and set to 0 otherwise.

Private data chunk
ID = privateData
Multiplicity Name Description Values Size
1 sourceType Type of source file
0 = AIFF
1 = WAVE
2 bytes
1 adler32 Adler-32 checksum of private data   4 bytes
1 numSourceChunks Number of sourceChunks that follow 1..231−1 4 bytes
1..* sourceChunk Chunk ID   4 bytes
Chunk size 0..231−1 4 bytes
0..1 data Compressed private data   n bytes

Table 3.5

Although the content of critical chunks is not included in the private data chunk, the chunks are included in the list of sourceChunks with their size set to zero, so that their position relative to the ancillary chunks is known when the ONDA file is expanded.

3.5  Data block size chunk (optional)

An Onda file may contain one data block size chunk, whose identifier is "dataBlockSize".

The data block size chunk contains the sizes of the data blocks in the data chunk. The block sizes can be converted to offsets to allow the data blocks to be accessed randomly. They are not required for expanding the compressed sample data, so the dataBlockSize chunk can be omitted from an Onda file that is to be used only for archival purposes.

To reduce the size of a dataBlockSize chunk, the sizes of the data blocks (in bits) are stored as an array of differences (deltaSizes) from a base size (baseSize). Each element in the deltaSizes array is a signed integer value, which, when added to baseSize, gives the size in bits of the corresponding data block in the data chunk. If random access to the data blocks in an Onda file is required, an array of offsets to the data blocks can be constructed from the deltaSizes array when the file is read.

The Onda application does not currently generate dataBlockSize chunks.

Data block size chunk
ID = dataBlockSize
Multiplicity Name Description Size
1 baseSize Base size of data blocks, bits 2 bytes
1 elementSize Size of elements in deltaSizes array, bytes 2 bytes
1 deltaSizes Array of n differences between block sizes and baseSize, bits n × elementSize bytes

Table 3.6

Appendix A:  Chunk size in IFF and RIFF files

The IFF and RIFF are similar formats: an RIFF file (type ID = "RIFF") appears to be the same as an IFF form file (type ID = "FORM") with the byte order of the chunk size reversed. However, there is another important difference: the chunk size in an IFF file is a 32-bit signed integer, whereas the chunk size in an RIFF file is a 32-bit unsigned integer.

The author discovered the difference in the data type of the chunk size only after the initial release of the Onda application, which incorrectly treats the chunk size in RIFF (WAVE) files as a signed value. The mistake arose from information on WAVE files that the author obtained several years ago from an erroneous — and widely disseminated — source on the Web. (Along with other sources, it also incorrectly gave the data type of the chunk size of an IFF file as an unsigned value — a sort of complementary error to balance things out.)

Previous versions of this appendix contained links to "the definitive sources" of information on IFF and RIFF files (pages from Apple's and Microsoft's websites), along with a reminder of the "timeless piece of racecourse wisdom" about getting your information from the horse's mouth, not the horse's arse. Sadly, one of the horses seems to have closed its mouth for the last time, and the other is looking moribund: the Apple web page no longer exists, and the Microsoft page has been replaced with several RIFF-related pages, all of reduced usefulness.

File format Data type of chunk size Source of information
IFF 32-bit signed integer
(a) The specification of IFF by Electronic Arts ("EA IFF 85" Standard for Interchange Format Files), widely available on the Web.
(b) Archived Audio Interchange File Format (AIFF) specification.
RIFF 32-bit unsigned integer Microsoft, developer of the Resource Interchange File Format (RIFF).

One reason that the false information has survived for so long on the Web is that it becomes a practical problem for developers only when their software encounters IFF or RIFF files that are larger than 2 GiB.

The Onda application, which is written in Java, uses library routines for IFF and RIFF files that assume the size of a chunk to be a signed integer in both formats. As a consequence, it will not allow the compression of audio files that are larger than 2 GiB. (The old ONDA file format, which conforms to the IFF specification, is similarly limited to 2 GiB.)

Last modified: 2014-10-14