1///////////////////////////////////////////////////////////////////////////
2//
3// Copyright (c) 2004, Industrial Light & Magic, a division of Lucas
4// Digital Ltd. LLC
5//
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions are
10// met:
11// *       Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13// *       Redistributions in binary form must reproduce the above
14// copyright notice, this list of conditions and the following disclaimer
15// in the documentation and/or other materials provided with the
16// distribution.
17// *       Neither the name of Industrial Light & Magic nor the names of
18// its contributors may be used to endorse or promote products derived
19// from this software without specific prior written permission.
20//
21// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33///////////////////////////////////////////////////////////////////////////
34
35
36//-----------------------------------------------------------------------------
37//
38//	class PizCompressor
39//
40//-----------------------------------------------------------------------------
41
42#include <ImfPizCompressor.h>
43#include <ImfHeader.h>
44#include <ImfChannelList.h>
45#include <ImfHuf.h>
46#include <ImfWav.h>
47#include <ImfMisc.h>
48#include <ImathFun.h>
49#include <ImathBox.h>
50#include <Iex.h>
51#include <ImfIO.h>
52#include <ImfXdr.h>
53#include <ImfAutoArray.h>
54#include <string.h>
55#include <assert.h>
56
57namespace Imf {
58
59using Imath::divp;
60using Imath::modp;
61using Imath::Box2i;
62using Imath::V2i;
63using Iex::InputExc;
64
65namespace {
66
67//
68// Functions to compress the range of values in the pixel data
69//
70
71const int USHORT_RANGE = (1 << 16);
72const int BITMAP_SIZE  = (USHORT_RANGE >> 3);
73
74void
75bitmapFromData (const unsigned short data[/*nData*/],
76		int nData,
77		unsigned char bitmap[BITMAP_SIZE],
78		unsigned short &minNonZero,
79		unsigned short &maxNonZero)
80{
81    for (int i = 0; i < BITMAP_SIZE; ++i)
82	bitmap[i] = 0;
83
84    for (int i = 0; i < nData; ++i)
85	bitmap[data[i] >> 3] |= (1 << (data[i] & 7));
86
87    bitmap[0] &= ~1;			// zero is not explicitly stored in
88					// the bitmap; we assume that the
89					// data always contain zeroes
90    minNonZero = BITMAP_SIZE - 1;
91    maxNonZero = 0;
92
93    for (int i = 0; i < BITMAP_SIZE; ++i)
94    {
95	if (bitmap[i])
96	{
97	    if (minNonZero > i)
98		minNonZero = i;
99	    if (maxNonZero < i)
100		maxNonZero = i;
101	}
102    }
103}
104
105
106unsigned short
107forwardLutFromBitmap (const unsigned char bitmap[BITMAP_SIZE],
108		      unsigned short lut[USHORT_RANGE])
109{
110    int k = 0;
111
112    for (int i = 0; i < USHORT_RANGE; ++i)
113    {
114	if ((i == 0) || (bitmap[i >> 3] & (1 << (i & 7))))
115	    lut[i] = k++;
116	else
117	    lut[i] = 0;
118    }
119
120    return k - 1;	// maximum value stored in lut[],
121}			// i.e. number of ones in bitmap minus 1
122
123
124unsigned short
125reverseLutFromBitmap (const unsigned char bitmap[BITMAP_SIZE],
126		      unsigned short lut[USHORT_RANGE])
127{
128    int k = 0;
129
130    for (int i = 0; i < USHORT_RANGE; ++i)
131    {
132	if ((i == 0) || (bitmap[i >> 3] & (1 << (i & 7))))
133	    lut[k++] = i;
134    }
135
136    int n = k - 1;
137
138    while (k < USHORT_RANGE)
139	lut[k++] = 0;
140
141    return n;		// maximum k where lut[k] is non-zero,
142}			// i.e. number of ones in bitmap minus 1
143
144
145void
146applyLut (const unsigned short lut[USHORT_RANGE],
147	  unsigned short data[/*nData*/],
148	  int nData)
149{
150    for (int i = 0; i < nData; ++i)
151	data[i] = lut[data[i]];
152}
153
154
155} // namespace
156
157
158struct PizCompressor::ChannelData
159{
160    unsigned short *	start;
161    unsigned short *	end;
162    int			nx;
163    int			ny;
164    int			ys;
165    int			size;
166};
167
168
169PizCompressor::PizCompressor
170    (const Header &hdr,
171     int maxScanLineSize,
172     int numScanLines)
173:
174    Compressor (hdr),
175    _maxScanLineSize (maxScanLineSize),
176    _format (XDR),
177    _numScanLines (numScanLines),
178    _tmpBuffer (0),
179    _outBuffer (0),
180    _numChans (0),
181    _channels (hdr.channels()),
182    _channelData (0)
183{
184    _tmpBuffer = new unsigned short [maxScanLineSize * numScanLines / 2];
185    _outBuffer = new char [maxScanLineSize * numScanLines + 65536 + 8192];
186
187    const ChannelList &channels = header().channels();
188    bool onlyHalfChannels = true;
189
190    for (ChannelList::ConstIterator c = channels.begin();
191	 c != channels.end();
192	 ++c)
193    {
194	_numChans++;
195
196	assert (pixelTypeSize (c.channel().type) % pixelTypeSize (HALF) == 0);
197
198	if (c.channel().type != HALF)
199	    onlyHalfChannels = false;
200    }
201
202    _channelData = new ChannelData[_numChans];
203
204    const Box2i &dataWindow = hdr.dataWindow();
205
206    _minX = dataWindow.min.x;
207    _maxX = dataWindow.max.x;
208    _maxY = dataWindow.max.y;
209
210    //
211    // We can support uncompressed data in the machine's native format
212    // if all image channels are of type HALF, and if the Xdr and the
213    // native represenations of a half have the same size.
214    //
215
216    if (onlyHalfChannels && (sizeof (half) == pixelTypeSize (HALF)))
217	_format = NATIVE;
218}
219
220
221PizCompressor::~PizCompressor ()
222{
223    delete [] _tmpBuffer;
224    delete [] _outBuffer;
225    delete [] _channelData;
226}
227
228
229int
230PizCompressor::numScanLines () const
231{
232    return _numScanLines;
233}
234
235
236Compressor::Format
237PizCompressor::format () const
238{
239    return _format;
240}
241
242
243int
244PizCompressor::compress (const char *inPtr,
245			 int inSize,
246			 int minY,
247			 const char *&outPtr)
248{
249    return compress (inPtr,
250		     inSize,
251		     Box2i (V2i (_minX, minY),
252			    V2i (_maxX, minY + numScanLines() - 1)),
253		     outPtr);
254}
255
256
257int
258PizCompressor::compressTile (const char *inPtr,
259			     int inSize,
260			     Imath::Box2i range,
261			     const char *&outPtr)
262{
263    return compress (inPtr, inSize, range, outPtr);
264}
265
266
267int
268PizCompressor::uncompress (const char *inPtr,
269			   int inSize,
270			   int minY,
271			   const char *&outPtr)
272{
273    return uncompress (inPtr,
274		       inSize,
275		       Box2i (V2i (_minX, minY),
276			      V2i (_maxX, minY + numScanLines() - 1)),
277		       outPtr);
278}
279
280
281int
282PizCompressor::uncompressTile (const char *inPtr,
283			       int inSize,
284			       Imath::Box2i range,
285			       const char *&outPtr)
286{
287    return uncompress (inPtr, inSize, range, outPtr);
288}
289
290
291int
292PizCompressor::compress (const char *inPtr,
293			 int inSize,
294			 Imath::Box2i range,
295			 const char *&outPtr)
296{
297    //
298    // This is the compress function which is used by both the tiled and
299    // scanline compression routines.
300    //
301
302    //
303    // Special case �- empty input buffer
304    //
305
306    if (inSize == 0)
307    {
308	outPtr = _outBuffer;
309	return 0;
310    }
311
312    //
313    // Rearrange the pixel data so that the wavelet
314    // and Huffman encoders can process them easily.
315    //
316    // The wavelet and Huffman encoders both handle only
317    // 16-bit data, so 32-bit data must be split into smaller
318    // pieces.  We treat each 32-bit channel (UINT, FLOAT) as
319    // two interleaved 16-bit channels.
320    //
321
322    int minX = range.min.x;
323    int maxX = range.max.x;
324    int minY = range.min.y;
325    int maxY = range.max.y;
326
327    if (maxY > _maxY)
328        maxY = _maxY;
329
330    if (maxX > _maxX)
331        maxX = _maxX;
332
333    unsigned short *tmpBufferEnd = _tmpBuffer;
334    int i = 0;
335
336    for (ChannelList::ConstIterator c = _channels.begin();
337	 c != _channels.end();
338	 ++c, ++i)
339    {
340	ChannelData &cd = _channelData[i];
341
342	cd.start = tmpBufferEnd;
343	cd.end = cd.start;
344
345	cd.nx = numSamples (c.channel().xSampling, minX, maxX);
346	cd.ny = numSamples (c.channel().ySampling, minY, maxY);
347	cd.ys = c.channel().ySampling;
348
349	cd.size = pixelTypeSize (c.channel().type) / pixelTypeSize (HALF);
350
351	tmpBufferEnd += cd.nx * cd.ny * cd.size;
352    }
353
354    if (_format == XDR)
355    {
356	//
357	// Machine-independent (Xdr) data format
358	//
359
360	for (int y = minY; y <= maxY; ++y)
361	{
362	    for (int i = 0; i < _numChans; ++i)
363	    {
364		ChannelData &cd = _channelData[i];
365
366		if (modp (y, cd.ys) != 0)
367		    continue;
368
369		for (int x = cd.nx * cd.size; x > 0; --x)
370		{
371		    Xdr::read <CharPtrIO> (inPtr, *cd.end);
372		    ++cd.end;
373		}
374	    }
375	}
376    }
377    else
378    {
379	//
380	// Native, machine-dependent data format
381	//
382
383	for (int y = minY; y <= maxY; ++y)
384	{
385	    for (int i = 0; i < _numChans; ++i)
386	    {
387		ChannelData &cd = _channelData[i];
388
389		if (modp (y, cd.ys) != 0)
390		    continue;
391
392		int n = cd.nx * cd.size;
393		memcpy (cd.end, inPtr, n * sizeof (unsigned short));
394		inPtr  += n * sizeof (unsigned short);
395		cd.end += n;
396	    }
397	}
398    }
399
400    #if defined (DEBUG)
401
402	for (int i = 1; i < _numChans; ++i)
403	    assert (_channelData[i-1].end == _channelData[i].start);
404
405	assert (_channelData[_numChans-1].end == tmpBufferEnd);
406
407    #endif
408
409    //
410    // Compress the range of the pixel data
411    //
412
413    AutoArray <unsigned char, BITMAP_SIZE> bitmap;
414    unsigned short minNonZero;
415    unsigned short maxNonZero;
416
417    bitmapFromData (_tmpBuffer,
418		    tmpBufferEnd - _tmpBuffer,
419		    bitmap,
420		    minNonZero, maxNonZero);
421
422    AutoArray <unsigned short, USHORT_RANGE> lut;
423    unsigned short maxValue = forwardLutFromBitmap (bitmap, lut);
424    applyLut (lut, _tmpBuffer, tmpBufferEnd - _tmpBuffer);
425
426    //
427    // Store range compression info in _outBuffer
428    //
429
430    char *buf = _outBuffer;
431
432    Xdr::write <CharPtrIO> (buf, minNonZero);
433    Xdr::write <CharPtrIO> (buf, maxNonZero);
434
435    if (minNonZero <= maxNonZero)
436    {
437	Xdr::write <CharPtrIO> (buf, (char *) &bitmap[0] + minNonZero,
438				maxNonZero - minNonZero + 1);
439    }
440
441    //
442    // Apply wavelet encoding
443    //
444
445    for (int i = 0; i < _numChans; ++i)
446    {
447	ChannelData &cd = _channelData[i];
448
449	for (int j = 0; j < cd.size; ++j)
450	{
451	    wav2Encode (cd.start + j,
452			cd.nx, cd.size,
453			cd.ny, cd.nx * cd.size,
454			maxValue);
455	}
456    }
457
458    //
459    // Apply Huffman encoding; append the result to _outBuffer
460    //
461
462    char *lengthPtr = buf;
463    Xdr::write <CharPtrIO> (buf, int(0));
464
465    int length = hufCompress (_tmpBuffer, tmpBufferEnd - _tmpBuffer, buf);
466    Xdr::write <CharPtrIO> (lengthPtr, length);
467
468    outPtr = _outBuffer;
469    return buf - _outBuffer + length;
470}
471
472
473int
474PizCompressor::uncompress (const char *inPtr,
475			   int inSize,
476			   Imath::Box2i range,
477			   const char *&outPtr)
478{
479    //
480    // This is the cunompress function which is used by both the tiled and
481    // scanline decompression routines.
482    //
483
484    //
485    // Special case - empty input buffer
486    //
487
488    if (inSize == 0)
489    {
490	outPtr = _outBuffer;
491	return 0;
492    }
493
494    //
495    // Determine the layout of the compressed pixel data
496    //
497
498    int minX = range.min.x;
499    int maxX = range.max.x;
500    int minY = range.min.y;
501    int maxY = range.max.y;
502
503    if (maxY > _maxY)
504        maxY = _maxY;
505
506    if (maxX > _maxX)
507        maxX = _maxX;
508
509    unsigned short *tmpBufferEnd = _tmpBuffer;
510    int i = 0;
511
512    for (ChannelList::ConstIterator c = _channels.begin();
513	 c != _channels.end();
514	 ++c, ++i)
515    {
516	ChannelData &cd = _channelData[i];
517
518	cd.start = tmpBufferEnd;
519	cd.end = cd.start;
520
521	cd.nx = numSamples (c.channel().xSampling, minX, maxX);
522	cd.ny = numSamples (c.channel().ySampling, minY, maxY);
523	cd.ys = c.channel().ySampling;
524
525	cd.size = pixelTypeSize (c.channel().type) / pixelTypeSize (HALF);
526
527	tmpBufferEnd += cd.nx * cd.ny * cd.size;
528    }
529
530    //
531    // Read range compression data
532    //
533
534    unsigned short minNonZero;
535    unsigned short maxNonZero;
536
537    AutoArray <unsigned char, BITMAP_SIZE> bitmap;
538    memset (bitmap, 0, sizeof (unsigned char) * BITMAP_SIZE);
539
540    Xdr::read <CharPtrIO> (inPtr, minNonZero);
541    Xdr::read <CharPtrIO> (inPtr, maxNonZero);
542
543    if (maxNonZero >= BITMAP_SIZE)
544    {
545	throw InputExc ("Error in header for PIZ-compressed data "
546			"(invalid bitmap size).");
547    }
548
549    if (minNonZero <= maxNonZero)
550    {
551	Xdr::read <CharPtrIO> (inPtr, (char *) &bitmap[0] + minNonZero,
552			       maxNonZero - minNonZero + 1);
553    }
554
555    AutoArray <unsigned short, USHORT_RANGE> lut;
556    unsigned short maxValue = reverseLutFromBitmap (bitmap, lut);
557
558    //
559    // Huffman decoding
560    //
561
562    int length;
563    Xdr::read <CharPtrIO> (inPtr, length);
564
565    hufUncompress (inPtr, length, _tmpBuffer, tmpBufferEnd - _tmpBuffer);
566
567    //
568    // Wavelet decoding
569    //
570
571    for (int i = 0; i < _numChans; ++i)
572    {
573	ChannelData &cd = _channelData[i];
574
575	for (int j = 0; j < cd.size; ++j)
576	{
577	    wav2Decode (cd.start + j,
578			cd.nx, cd.size,
579			cd.ny, cd.nx * cd.size,
580			maxValue);
581	}
582    }
583
584    //
585    // Expand the pixel data to their original range
586    //
587
588    applyLut (lut, _tmpBuffer, tmpBufferEnd - _tmpBuffer);
589
590    //
591    // Rearrange the pixel data into the format expected by the caller.
592    //
593
594    char *outEnd = _outBuffer;
595
596    if (_format == XDR)
597    {
598	//
599	// Machine-independent (Xdr) data format
600	//
601
602	for (int y = minY; y <= maxY; ++y)
603	{
604	    for (int i = 0; i < _numChans; ++i)
605	    {
606		ChannelData &cd = _channelData[i];
607
608		if (modp (y, cd.ys) != 0)
609		    continue;
610
611		for (int x = cd.nx * cd.size; x > 0; --x)
612		{
613		    Xdr::write <CharPtrIO> (outEnd, *cd.end);
614		    ++cd.end;
615		}
616	    }
617	}
618    }
619    else
620    {
621	//
622	// Native, machine-dependent data format
623	//
624
625	for (int y = minY; y <= maxY; ++y)
626	{
627	    for (int i = 0; i < _numChans; ++i)
628	    {
629		ChannelData &cd = _channelData[i];
630
631		if (modp (y, cd.ys) != 0)
632		    continue;
633
634		int n = cd.nx * cd.size;
635		memcpy (outEnd, cd.end, n * sizeof (unsigned short));
636		outEnd += n * sizeof (unsigned short);
637		cd.end += n;
638	    }
639	}
640    }
641
642    #if defined (DEBUG)
643
644	for (int i = 1; i < _numChans; ++i)
645	    assert (_channelData[i-1].end == _channelData[i].start);
646
647	assert (_channelData[_numChans-1].end == tmpBufferEnd);
648
649    #endif
650
651    outPtr = _outBuffer;
652    return outEnd - _outBuffer;
653}
654
655
656} // namespace Imf
657