File: itsex.c

package info (click to toggle)
ocp 1:0.1.21-5
  • links: PTS
  • area: main
  • in suites: bullseye, buster
  • size: 5,528 kB
  • sloc: ansic: 91,461; cpp: 9,729; sh: 3,119; makefile: 2,493
file content (450 lines) | stat: -rw-r--r-- 15,263 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
/* OpenCP Module Player
 * copyright (c) '94-'10 Niklas Beisert <nbeisert@physik.tu-muenchen.de>
 *
 * IT 2.14/2.15 sample decompression routines.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * revision history: (please note changes here)
 *  -kb980717    Tammo Hinrichs <kb@nwn.de>
 *    -first release


 * Well.
 * The existance of this file, and the fact that you're just reading this
 * text may upset some people. I know this. I also know about the risks of
 * not only having coded this, but freely releasing it to the public. But
 * well, if this is the end of my life, why not, at least i have done some-
 * thing good to all player coders / game developers with IT fanatic mu-
 * sicians etc. ;)

 * And to make it even worse: A short (?) description of what the routines
 * in this file do.

 * It's all about sample compression. Due to the rather "analog" behaviour
 * of audio streams, it's not always possible to gain high reduction rates
 * with generic compression algorithms. So the idea is to find an algorithm
 * which is specialized for the kind of data we're actually dealing with:
 * mono sample data.

 * in fact, PKZIP etc. is still somewhat better than this algorithm in most
 * cases, but the advantage of this is it's decompression speed which might
 * enable sometimes players or even synthesizer chips to decompress IT
 * samples in real-time. And you can still pack these compressed samples with
 * "normal" algorithms and get better results than these algorothms would
 * ever achieve alone.

 * some assumptions i made (and which also pulse made - and without which it
 * would have been impossible for me to figure out the algorithm) :

 * - it must be possible to find values which are found more often in the
 *   file than others. Thus, it's possible to somehow encode the values
 *   which we come across more often with less bits than the rest.
 * - In general, you can say that low values (considering distance to
 *   the null line) are found more often, but then, compression results
 *   would heavily depend on signal amplitude and DC offsets and such.
 * - But: ;)
 * - higher frequencies have generally lower amplitudes than low ones, just
 *   due to the nature of sound and our ears
 * - so we could somehow filter the signal to decrease the low frequencies'
 *   amplitude, thus resulting in lesser overall amplitude, thus again resul-
 *   ting in better ratios, if we take the above thoughts into consideration.
 * - every signal can be split into a sum of single frequencies, that is a
 *   sum of a(f)*sin(f*t) terms (just believe me if you don't already know).
 * - if we differentiate this sum, we get a sum of (a(f)*f)*cos(f*t). Due to
 *   f being scaled to the nyquist of the sample frequency, it's always
 *   between 0 and 1, and we get just what we want - we decrease the ampli-
 *   tude of the low frequencies (and shift the signal's phase by 90 degrees,
 *   but that's just a side-effect that doesn't have to interest us)
 * - the backwards way is simple integrating over the data and is completely
 *   lossless. good.
 * - so how to differentiate or integrate a sample stream? the solution is
 *   simple: we simply use deltas from one sample to the next and have the
 *   perfectly numerically differentiated curve. When we decompress, we
 *   just add the value we get to the last one and thus restore the original
 *   signal.
 * - then, we assume that the "-1"st sample value is always 0 to avoid nasty
 *   DC offsets when integrating.

 * ok. now we have a sample stream which definitely contains more low than
 * high values. How do we compress it now?

 * Pulse had chosen a quite unusual, but effective solution: He encodes the
 * values with a specific "bit width" and places markers between the values
 * which indicate if this width would change. He implemented three different
 * methods for that, depending on the bit width we actually have (i'll write
 * it down for 8 bit samples, values which change for 16bit ones are in these
 * brackets [] ;):

 * method 1: 1 to 6 bits
 * * there are two possibilities (example uses a width of 6)
 *   - 100000 (a one with (width-1) zeroes ;) :
 *     the next 3 [4] bits are read, incremented and used as new width...
 *     and as it would be completely useless to switch to the same bit
 *     width again, any value equal or greater the actual width is
 *     incremented, thus resulting in a range from 1-9 [1-17] bits (which
 *     we definitely need).
 *   - any other value is expanded to a signed byte [word], integrated
 *     and stored.
 * method 2: 7 to 8 [16] bits
 * * again two possibilities (this time using a width of eg. 8 bits)
 *   - 01111100 to 10000011 [01111000 to 10000111] :
 *     this value will be subtracted by 01111011 [01110111], thus resulting
 *     again in a 1-8 [1-16] range which will be expanded to 1-9 [1-17] in
 *     the same manner as above
 *   - any other value is again expanded (if necessary), integrated and
 *     stored
 * method 3: 9 [17] bits
 * * this time it depends on the highest bit:
 *   - if 0, the last 8 [16] bits will be integrated and stored
 *   - if 1, the last 8 [16] bits (+1) will be used as new bit width.
 * any other width isnt supposed to exist and will result in a premature
 * exit of the decompressor.

 * Few annotations:
 * - The compressed data is processed in blocks of 0x8000 bytes. I dont
 *   know the reason of this (it's definitely NOT better concerning compres-
 *   sion ratio), i just think that it has got something to do with Pulse's
 *   EMS memory handling or such. Anyway, this was really nasty to find
 *   out ;)
 * - The starting bit width is 9 [17]
 * - IT2.15 compression simply doubles the differentiation/integration
 *   of the signal, thus eliminating low frequencies some more and turning
 *   the signal phase to 180 degrees instead of 90 degrees which can eliminate
 *   some signal peaks here and there - all resulting in a somewhat better ratio.

 * ok, but now lets start... but think before you easily somehow misuse
 * this code, the algorithm is (C) Jeffrey Lim aka Pulse... and my only
 * intention is to make IT's file format more open to the Tracker Community
 * and especially the rest of the scene. Trackers ALWAYS were open standards,
 * which everyone was able (and WELCOME) to adopt, and I don't think this
 * should change. There are enough other things in the computer world
 * which did, let's just not be mainstream, but open-minded. Thanks.

 *                    Tammo Hinrichs [ KB / T.O.M / PuRGE / Smash Designs ]



 * ----------------------------------------------------------------------
 *  includes...
 * ----------------------------------------------------------------------
 */

#if 0
#define NULL 0          /* added by doj to get rid of #include <malloc.h>
			 *
			 * glibc it exists in stdio, and we need that file for
			 * (FILE *), sorry dudes - Stian */
#endif
#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "types.h"
#include "stuff/imsrtns.h"
#include "itplay.h"


/* ----------------------------------------------------------------------
 *  some helpful typedefs which are lame, but so am I :)
 * ----------------------------------------------------------------------
 */

typedef uint8_t   byte;
typedef int8_t    sbyte;
typedef uint16_t  word;
typedef int16_t   sword;
typedef uint32_t  dword;

/* ----------------------------------------------------------------------
 *  auxiliary routines to get bits from the input stream
 * ----------------------------------------------------------------------
 */

static uint8_t *sourcebuffer = NULL;
static uint8_t *ibuf         = NULL; /* actual reading position */
static uint32_t bitlen;
static uint8_t bitnum;

static inline uint32_t readbits(uint8_t n)
{
	uint32_t retval=0;
	int offset = 0;
	while (n)
	{
		int m=n;

		if (!bitlen)
		{
			fprintf(stderr, "readbits: ran out of buffer\n");
			return 0;
		}

		if (m>bitnum)
			m=bitnum;
		retval|=(*ibuf&((1L<<m)-1))<<offset;
		*ibuf>>=m;
		n-=m;
		offset+=m;
		if ( ! ( bitnum-=m ) )
		{
			bitlen--;
			ibuf++;
			bitnum=8;
		}
	}
	return retval;
}
static int readblock(FILE *f)  /* gets block of compressed data from file */
{
	uint16_t size;
	if (fread(&size, sizeof(uint16_t), 1, f) != 1)  /* block layout : word size, <size> bytes data */
		return 0;
	size = uint16_little (size);
	if ( ! size )
		return 0;
	if (!(sourcebuffer = malloc(size)))
		return 0;
	if (fread(sourcebuffer, size, 1, f) != 1)
	{
		free(sourcebuffer);
		sourcebuffer=NULL; /* Just looks better to have it present */
		return 0;
	}
	ibuf=sourcebuffer;
	bitnum=8;
	bitlen=size;
	return 1;
}


static int freeblock(void)          /* frees that block again */
{
	if (sourcebuffer)
		free(sourcebuffer);
	sourcebuffer=NULL;
	return 1;
}


/* ----------------------------------------------------------------------
 *  decompression routines
 * ----------------------------------------------------------------------

 * decompresses 8-bit sample (params : file, outbuffer, lenght of
 *                                     uncompressed sample, IT2.15
 *                                     compression flag
 *                            returns: status                     )
 */

int __attribute__ ((visibility ("internal"))) decompress8 (FILE *module, void *dst, int len, char it215)
{
	sbyte *destbuf;   /* the destination buffer which will be returned */

	word blklen;      /* length of compressed data block in samples */
	word blkpos;      /* position in block */
	byte width;       /* actual "bit width" */
	word value;       /* value read from file to be processed */
	sbyte d1, d2;     /* integrator buffers (d2 for it2.15) */
	sbyte *destpos;

	destbuf = (sbyte *)dst;
	if (!destbuf)
		return 0;

	memsetb(destbuf,0,len);
	destpos=destbuf; /* position in output buffer */

	/* now unpack data till the dest buffer is full */
	while (len)
	{
		/* read a new block of compressed data and reset variables */

		if (!readblock(module))
			return 0;
		blklen=(len<0x8000)?len:0x8000;
		blkpos=0;

		width=9;  /* start with width of 9 bits */
		d1=d2=0;  /* reset integrator buffers */

		/* now uncompress the data block */
		while (blkpos<blklen)
		{
			sbyte v;

			value = readbits(width); /* read bits */

			if (width<7) /* method 1 (1-6 bits) */
			{
				if (value==(1<<(width-1))) /* check for "100..." */
				{
					value = readbits(3)+1;                /* yes -> read new width; */
					width = (value<width)?value:value+1;  /* and expand it */
					continue;                             /* ... next value */
				}
			} else if (width<9) /* method 2 (7-8 bits) */
			{
				byte border = (0xFF>>(9-width)) - 4;  /* lower border for width chg */

				if (value>border && value <=(border+8))
				{
					value-=border;                        /* convert width to 1-8 */
					width = (value<width)?value:value+1;  /* and expand it */
					continue;                             /* ... next value */
				}
			} else if (width==9) /* method 3 (9 bits) */
			{
				if (value & 0x100) /* bit 8 set? */
				{
					width=(value+1)&0xff; /* new width... */
					continue;             /* ... and next value */
				}
			} else { /* illegal width, abort */
				freeblock();
				return 0;
			}

			/* now expand value to signed byte */
			/*      sbyte v;  // sample value */
			if (width<8)
			{
				byte shift=8-width;
				v = (value<<shift);
				v>>=shift;
			} else
				v = (sbyte)value;

			/* integrate upon the sample values */
			d1+=v;
			d2+=d1;

			/* ... and store it into the buffer */
			*(destpos++)=it215?d2:d1;
			blkpos++;

		}

		/* now subtract block lenght from total length and go on */
		freeblock();
		len-=blklen;
	}

	return 1;
}




/* decompresses 16-bit sample (params : file, outbuffer, lenght of
 *                                      uncompressed sample, IT2.15
 *                                      compression flag
 *                             returns: status                     )
 */
int __attribute__ ((visibility ("internal"))) decompress16(FILE *module, void *dst, int len, char it215)
{
	sword *destbuf;   /* the destination buffer which will be returned */

	word blklen;      /* length of compressed data block in samples */
	word blkpos;      /* position in block */
	byte width;       /* actual "bit width" */
	dword value;      /* value read from file to be processed */
	sword d1, d2;     /* integrator buffers (d2 for it2.15) */
	sword *destpos;

	destbuf = (sword *)dst;
	if (!destbuf)
		return 0;

	memsetw(destbuf,0,len);
	destpos=destbuf; /* position in output buffer */

	/* now unpack data till the dest buffer is full */
	while (len)
	{

		/* read a new block of compressed data and reset variables */

		if (!readblock(module))
			return 0;
		blklen=(len<0x4000)?len:0x4000; /* 0x4000 samples => 0x8000 bytes again */
		blkpos=0;

		width=17; /* start with width of 17 bits */
		d1=d2=0;  /* reset integrator buffers */

		/* now uncompress the data block */
		while (blkpos<blklen)
		{
			sword v;

			value = readbits(width); /* read bits */

			if (width<7) /* method 1 (1-6 bits) */
			{
				if (value==((unsigned)1<<(width-(unsigned)1))) /* check for "100..." */
				{
					value = readbits(4)+1;                /* yes -> read new width; */
					width = (value<width)?value:value+1;  /* and expand it */
					continue;                             /* ... next value */
				}
			} else if (width<17) /* method 2 (7-16 bits) */
			{
				word border = (0xFFFF>>(17-width)) - 8;  /* lower border for width chg */

				if ((value>border) && (value <=(border+(unsigned)16))) /* STIAN NOTE, Logic has changed here, 20081110 */
				{
					value-=border;                        /* convert width to 1-8 */
					width = (value<width)?value:value+1;  /* and expand it */
					continue;                             /* ... next value */
				}
			} else if (width==17) /* method 3 (17 bits) */
			{
				if (value&0x10000) /* bit 16 set? */
				{
					width=(value+1)&0xff; /* new width... */
					continue;             /* ... and next value */
				}
			} else { /* illegal width, abort */
				freeblock();
				return 0;
			}

			/* now expand value to signed word */
			/* sword v; // sample value */
			if (width<16)
			{
				byte shift=16-width;
				v = (value<<shift);
				v>>=shift;
			} else
				v = (sword)value;

			/* integrate upon the sample values */
			d1+=v;
			d2+=d1;

			/* ... and store it into the buffer */
			*(destpos++)=it215?d2:d1;
			blkpos++;
		}

		/* now subtract block lenght from total length and go on */
		freeblock();
		len-=blklen;
	}

	return 1;
}