WebSVN – Games.Descent – Blame – /common/2d/rle.cpp

Rev	Author	Line No.	Line
1	pmbaty	1	/*
		2	* Portions of this file are copyright Rebirth contributors and licensed as
		3	* described in COPYING.txt.
		4	* Portions of this file are copyright Parallax Software and licensed
		5	* according to the Parallax license below.
		6	* See COPYING.txt for license details.
		7
		8	THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
		9	SOFTWARE CORPORATION ("PARALLAX"). PARALLAX, IN DISTRIBUTING THE CODE TO
		10	END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
		11	ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
		12	IN USING, DISPLAYING, AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
		13	SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
		14	FREE PURPOSES. IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
		15	CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES. THE END-USER UNDERSTANDS
		16	AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
		17	COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION. ALL RIGHTS RESERVED.
		18	*/
		19
		20	/*
		21	*
		22	* Routines to do run length encoding/decoding
		23	* on bitmaps.
		24	*
		25	*/
		26
		27	#include <algorithm>
		28	#include <stdlib.h>
		29	#include <stdio.h>
		30	#include <string.h>
		31
		32	#include "pstypes.h"
		33	#include "u_mem.h"
		34	#include "gr.h"
		35	#include "grdef.h"
		36	#include "dxxerror.h"
		37	#include "rle.h"
		38	#include "byteutil.h"
		39
		40	#include "compiler-range_for.h"
		41	#include "d_range.h"
		42
		43	namespace dcx {
		44
		45	constexpr uint8_t RLE_CODE = 0xe0;
		46	constexpr uint8_t NOT_RLE_CODE = 0x1f;
		47	static_assert((RLE_CODE \| NOT_RLE_CODE) == 0xff, "RLE mask error");
		48	static inline int IS_RLE_CODE(const uint8_t &x)
		49	{
		50	return (x & RLE_CODE) == RLE_CODE;
		51	}
		52	#define rle_stosb(_dest, _len, _color) memset(_dest,_color,_len)
		53
		54	uint8_t gr_rle_decode(const color_palette_index sb, color_palette_index *db, const rle_position_t e)
		55	{
		56	using std::advance;
		57	using std::distance;
		58	for (; sb != e.src;)
		59	{
		60	auto p = sb;
		61	color_palette_index c;
		62	for (; c = *p, !IS_RLE_CODE(c);)
		63	if (++p == e.src)
		64	return db;
		65	const size_t count = (c & NOT_RLE_CODE);
		66	const size_t cn = std::min<size_t>(distance(sb, p), distance(db, e.dst));
		67	memcpy(db, sb, cn);
		68	advance(db, cn);
		69	if (!count)
		70	break;
		71	advance(sb, cn);
		72	if (sb == e.src \|\| db == e.dst \|\| count > static_cast<size_t>(distance(db, e.dst)))
		73	break;
		74	if (++ sb == e.src)
		75	break;
		76	std::fill_n(db, count, *sb++);
		77	advance(db, count);
		78	}
		79	return db;
		80	}
		81
		82	#if !DXX_USE_OGL
		83	// Given pointer to start of one scanline of rle data, uncompress it to
		84	// dest, from source pixels x1 to x2.
		85	void gr_rle_expand_scanline_masked(uint8_t dest, const uint8_t src, int x1, int x2)
		86	{
		87	int i = 0;
		88	ubyte count;
		89	ubyte color=0;
		90
		91	if ( x2 < x1 ) return;
		92
		93	count = 0;
		94	while ( i < x1 ) {
		95	color = *src++;
		96	if ( color == RLE_CODE ) return;
		97	if ( IS_RLE_CODE(color) ) {
		98	count = color & NOT_RLE_CODE;
		99	color = *src++;
		100	} else {
		101	// unique
		102	count = 1;
		103	}
		104	i += count;
		105	}
		106	count = i - x1;
		107	i = x1;
		108	// we know have '*count' pixels of 'color'.
		109
		110	if ( x1+count > x2 ) {
		111	count = x2-x1+1;
		112	if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
		113	return;
		114	}
		115
		116	if ( color != TRANSPARENCY_COLOR ) rle_stosb( dest, count, color );
		117	dest += count;
		118	i += count;
		119
		120	while( i <= x2 )
		121	{
		122	color = *src++;
		123	if ( color == RLE_CODE ) return;
		124	if ( IS_RLE_CODE(color) ) {
		125	count = color & NOT_RLE_CODE;
		126	color = *src++;
		127	} else {
		128	// unique
		129	count = 1;
		130	}
		131	// we know have '*count' pixels of 'color'.
		132	if ( i+count <= x2 ) {
		133	if ( color != 255 )rle_stosb( dest, count, color );
		134	i += count;
		135	dest += count;
		136	} else {
		137	count = x2-i+1;
		138	if ( color != 255 )rle_stosb( dest, count, color );
		139	i += count;
		140	dest += count;
		141	}
		142	}
		143	}
		144	#endif
		145
		146	void gr_rle_expand_scanline(uint8_t dest, const uint8_t src, int x1, int x2)
		147	{
		148	int i = 0;
		149	ubyte count;
		150	ubyte color=0;
		151
		152	if ( x2 < x1 ) return;
		153
		154	count = 0;
		155	while ( i < x1 ) {
		156	color = *src++;
		157	if ( color == RLE_CODE ) return;
		158	if ( IS_RLE_CODE(color) ) {
		159	count = color & NOT_RLE_CODE;
		160	color = *src++;
		161	} else {
		162	// unique
		163	count = 1;
		164	}
		165	i += count;
		166	}
		167	count = i - x1;
		168	i = x1;
		169	// we know have '*count' pixels of 'color'.
		170
		171	if ( x1+count > x2 ) {
		172	count = x2-x1+1;
		173	rle_stosb( dest, count, color );
		174	return;
		175	}
		176
		177	rle_stosb( dest, count, color );
		178	dest += count;
		179	i += count;
		180
		181	while( i <= x2 ) {
		182	color = *src++;
		183	if ( color == RLE_CODE ) return;
		184	if ( IS_RLE_CODE(color) ) {
		185	count = color & (~RLE_CODE);
		186	color = *src++;
		187	} else {
		188	// unique
		189	count = 1;
		190	}
		191	// we know have '*count' pixels of 'color'.
		192	if ( i+count <= x2 ) {
		193	rle_stosb( dest, count, color );
		194	i += count;
		195	dest += count;
		196	} else {
		197	count = x2-i+1;
		198	rle_stosb( dest, count, color );
		199	i += count;
		200	dest += count;
		201	}
		202	}
		203	}
		204
		205	static std::ptrdiff_t gr_rle_encode( int org_size, const uint8_t src, ubyte dest )
		206	{
		207	ubyte c, oc;
		208	ubyte count;
		209	uint8_t *dest_start;
		210
		211	dest_start = dest;
		212	oc = *src++;
		213	count = 1;
		214
		215	if (org_size > 0)
		216	for (uint_fast32_t i = org_size; --i;)
		217	{
		218	c = *src++;
		219	if ( c!=oc ) {
		220	if ( count ) {
		221	if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
		222	*dest++ = oc;
		223	Assert( oc != RLE_CODE );
		224	} else {
		225	count \|= RLE_CODE;
		226	*dest++ = count;
		227	*dest++ = oc;
		228	}
		229	}
		230	oc = c;
		231	count = 0;
		232	}
		233	count++;
		234	if ( count == NOT_RLE_CODE ) {
		235	count \|= RLE_CODE;
		236	*dest++=count;
		237	*dest++=oc;
		238	count = 0;
		239	}
		240	}
		241	if (count) {
		242	if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
		243	*dest++ = oc;
		244	Assert( oc != RLE_CODE );
		245	} else {
		246	count \|= RLE_CODE;
		247	*dest++ = count;
		248	*dest++ = oc;
		249	}
		250	}
		251	*dest++ = RLE_CODE;
		252
		253	return dest-dest_start;
		254	}
		255
		256	static unsigned gr_rle_getsize(int org_size, const uint8_t *src)
		257	{
		258	ubyte c, oc;
		259	ubyte count;
		260	int dest_size=0;
		261
		262	oc = *src++;
		263	count = 1;
		264
		265	if (org_size > 0)
		266	for (uint_fast32_t i = org_size; --i;)
		267	{
		268	c = *src++;
		269	if ( c!=oc ) {
		270	if ( count ) {
		271	if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
		272	dest_size++;
		273	} else {
		274	dest_size++;
		275	dest_size++;
		276	}
		277	}
		278	oc = c;
		279	count = 0;
		280	}
		281	count++;
		282	if ( count == NOT_RLE_CODE ) {
		283	dest_size++;
		284	dest_size++;
		285	count = 0;
		286	}
		287	}
		288	if (count) {
		289	if ( (count==1) && (! IS_RLE_CODE(oc)) ) {
		290	dest_size++;
		291	} else {
		292	dest_size++;
		293	dest_size++;
		294	}
		295	}
		296	dest_size++;
		297
		298	return dest_size;
		299	}
		300
		301	int gr_bitmap_rle_compress(grs_bitmap &bmp)
		302	{
		303	int doffset;
		304	int large_rle = 0;
		305
		306	// first must check to see if this is large bitmap.
		307
		308	const uint_fast32_t bm_h = bmp.bm_h;
		309	const uint_fast32_t bm_w = bmp.bm_w;
		310	range_for (const uint_fast32_t y, xrange(bm_h))
		311	{
		312	auto d1 = gr_rle_getsize(bm_w, &bmp.get_bitmap_data()[bm_w * y]);
		313	if (d1 > 255) {
		314	large_rle = BM_FLAG_RLE_BIG;
		315	break;
		316	}
		317	}
		318
		319	RAIIdmem<uint8_t[]> rle_data;
		320	MALLOC(rle_data, uint8_t[], MAX_BMP_SIZE(bm_w, bm_h));
		321	if (!rle_data) return 0;
		322	if (!large_rle)
		323	doffset = 4 + bm_h;
		324	else
		325	doffset = 4 + (2 * bm_h); // each row of rle'd bitmap has short instead of byte offset now
		326
		327	range_for (const uint_fast32_t y, xrange(bm_h))
		328	{
		329	auto d1 = gr_rle_getsize(bm_w, &bmp.get_bitmap_data()[bm_w * y]);
		330	if ( ((doffset+d1) > bmp.bm_w*bmp.bm_h) \|\| (d1 > (large_rle?32767:255) ) ) {
		331	return 0;
		332	}
		333	const auto d = gr_rle_encode( bmp.bm_w, &bmp.get_bitmap_data()[bmp.bm_w*y], &rle_data[doffset] );
		334	Assert( d==d1 );
		335	doffset += d;
		336	if (large_rle)
		337	PUT_INTEL_SHORT(&rle_data[(y*2)+4], static_cast<short>(d));
		338	else
		339	rle_data[y+4] = d;
		340	}
		341	memcpy(bmp.get_bitmap_data(), &doffset, 4);
		342	memcpy(&bmp.get_bitmap_data()[4], &rle_data.get()[4], doffset - 4);
		343	bmp.add_flags(BM_FLAG_RLE \| large_rle);
		344	return 1;
		345	}
		346
		347	namespace {
		348
		349	struct rle_cache_element
		350	{
		351	const grs_bitmap *rle_bitmap;
		352	grs_bitmap_ptr expanded_bitmap;
		353	int last_used;
		354	};
		355
		356	}
		357
		358	static int rle_cache_initialized;
		359	static int rle_counter;
		360	static int rle_next;
		361	static std::array<rle_cache_element, 32> rle_cache;
		362
		363	void rle_cache_close(void)
		364	{
		365	if (rle_cache_initialized) {
		366	rle_cache_initialized = 0;
		367	range_for (auto &i, rle_cache)
		368	i.expanded_bitmap.reset();
		369	}
		370	}
		371
		372	static void rle_cache_init()
		373	{
		374	rle_cache = {};
		375	rle_cache_initialized = 1;
		376	}
		377
		378	void rle_cache_flush()
		379	{
		380	range_for (auto &i, rle_cache)
		381	{
		382	i.rle_bitmap = NULL;
		383	i.last_used = 0;
		384	}
		385	}
		386
		387	static void rle_expand_texture_sub(const grs_bitmap &bmp, grs_bitmap &rle_temp_bitmap_1)
		388	{
		389	auto sbits = &bmp.get_bitmap_data()[4 + bmp.bm_h];
		390	auto dbits = rle_temp_bitmap_1.get_bitmap_data();
		391
		392	rle_temp_bitmap_1.set_flags(bmp.get_flags() & (~BM_FLAG_RLE));
		393
		394	for (int i=0; i < bmp.bm_h; i++ ) {
		395	gr_rle_decode(sbits, dbits, rle_end(bmp, rle_temp_bitmap_1));
		396	sbits += static_cast<int>(bmp.bm_data[4+i]);
		397	dbits += bmp.bm_w;
		398	}
		399	}
		400
		401
		402	grs_bitmap *_rle_expand_texture(const grs_bitmap &bmp)
		403	{
		404	int lowest_count, lc;
		405
		406	if (!rle_cache_initialized) rle_cache_init();
		407
		408	Assert(!(bmp.get_flag_mask(BM_FLAG_PAGED_OUT)));
		409
		410	lc = rle_counter;
		411	rle_counter++;
		412
		413	if (rle_counter < 0)
		414	rle_counter = 0;
		415
		416	if ( rle_counter < lc ) {
		417	rle_cache_flush();
		418	}
		419
		420	lowest_count = rle_cache[rle_next].last_used;
		421	auto least_recently_used = &rle_cache[rle_next];
		422	rle_next++;
		423	if (rle_next >= rle_cache.size())
		424	rle_next = 0;
		425
		426	range_for (auto &i, rle_cache)
		427	{
		428	if (i.rle_bitmap == &bmp)
		429	{
		430	i.last_used = rle_counter;
		431	return i.expanded_bitmap.get();
		432	}
		433	if (i.last_used < lowest_count)
		434	{
		435	lowest_count = (least_recently_used = &i)->last_used;
		436	}
		437	}
		438
		439	least_recently_used->expanded_bitmap = gr_create_bitmap(bmp.bm_w, bmp.bm_h);
		440	rle_expand_texture_sub(bmp, *least_recently_used->expanded_bitmap.get());
		441	least_recently_used->rle_bitmap = &bmp;
		442	least_recently_used->last_used = rle_counter;
		443	return least_recently_used->expanded_bitmap.get();
		444	}
		445
		446	#if !DXX_USE_OGL
		447	void gr_rle_expand_scanline_generic(grs_canvas &canvas, grs_bitmap &dest, int dx, const int dy, const uint8_t *src, const int x1, const int x2)
		448	{
		449	int i = 0;
		450	int count;
		451	ubyte color=0;
		452
		453	if ( x2 < x1 ) return;
		454
		455	count = 0;
		456	while ( i < x1 ) {
		457	color = *src++;
		458	if ( color == RLE_CODE ) return;
		459	if ( IS_RLE_CODE(color) ) {
		460	count = color & NOT_RLE_CODE;
		461	color = *src++;
		462	} else {
		463	// unique
		464	count = 1;
		465	}
		466	i += count;
		467	}
		468	count = i - x1;
		469	i = x1;
		470	// we know have '*count' pixels of 'color'.
		471
		472	if ( x1+count > x2 ) {
		473	count = x2-x1+1;
		474	for ( int j=0; j<count; j++ )
		475	gr_bm_pixel(canvas, dest, dx++, dy, color);
		476	return;
		477	}
		478
		479	for ( int j=0; j<count; j++ )
		480	gr_bm_pixel(canvas, dest, dx++, dy, color);
		481	i += count;
		482
		483	while( i <= x2 ) {
		484	color = *src++;
		485	if ( color == RLE_CODE ) return;
		486	if ( IS_RLE_CODE(color) ) {
		487	count = color & NOT_RLE_CODE;
		488	color = *src++;
		489	} else {
		490	// unique
		491	count = 1;
		492	}
		493	// we know have '*count' pixels of 'color'.
		494	if ( i+count <= x2 ) {
		495	} else {
		496	count = x2-i+1;
		497	}
		498	for (unsigned j = 0; j < count; ++j)
		499	gr_bm_pixel(canvas, dest, dx++, dy, color);
		500	i += count;
		501	}
		502	}
		503	#endif
		504
		505	/*
		506	* swaps entries 0 and 255 in an RLE bitmap without uncompressing it
		507	*/
		508	void rle_swap_0_255(grs_bitmap &bmp)
		509	{
		510	int len, rle_big;
		511	unsigned char *start;
		512	unsigned short line_size;
		513
		514	rle_big = bmp.get_flag_mask(BM_FLAG_RLE_BIG);
		515
		516	RAIIdmem<uint8_t[]> temp;
		517	MALLOC(temp, uint8_t[], MAX_BMP_SIZE(bmp.bm_w, bmp.bm_h));
		518
		519	const std::size_t pointer_offset = rle_big ? 4 + 2 * bmp.bm_h : 4 + bmp.bm_h;
		520	auto ptr = &bmp.bm_data[pointer_offset];
		521	auto ptr2 = &temp[pointer_offset];
		522	for (int i = 0; i < bmp.bm_h; i++) {
		523	start = ptr2;
		524	if (rle_big)
		525	line_size = GET_INTEL_SHORT(&bmp.bm_data[4 + 2 * i]);
		526	else
		527	line_size = bmp.bm_data[4 + i];
		528	for (int j = 0; j < line_size; j++) {
		529	if ( ! IS_RLE_CODE(ptr[j]) ) {
		530	if (ptr[j] == 0) {
		531	*ptr2++ = RLE_CODE \| 1;
		532	*ptr2++ = 255;
		533	} else
		534	*ptr2++ = ptr[j];
		535	} else {
		536	*ptr2++ = ptr[j];
		537	if ((ptr[j] & NOT_RLE_CODE) == 0)
		538	break;
		539	j++;
		540	if (ptr[j] == 0)
		541	*ptr2++ = 255;
		542	else if (ptr[j] == 255)
		543	*ptr2++ = 0;
		544	else
		545	*ptr2++ = ptr[j];
		546	}
		547	}
		548	if (rle_big) // set line size
		549	PUT_INTEL_SHORT(&temp[4 + 2 * i], static_cast<uint16_t>(ptr2 - start));
		550	else
		551	temp[4 + i] = ptr2 - start;
		552	ptr += line_size; // go to next line
		553	}
		554	len = ptr2 - temp.get();
		555	memcpy(bmp.get_bitmap_data(), &len, 4);
		556	memcpy(&bmp.get_bitmap_data()[4], &temp.get()[4], len - 4);
		557	}
		558
		559	/*
		560	* remaps all entries using colormap in an RLE bitmap without uncompressing it
		561	*/
		562	void rle_remap(grs_bitmap &bmp, std::array<color_palette_index, 256> &colormap)
		563	{
		564	int len, rle_big;
		565	unsigned short line_size;
		566
		567	rle_big = bmp.get_flag_mask(BM_FLAG_RLE_BIG);
		568
		569	RAIIdmem<color_palette_index[]> temp;
		570	MALLOC(temp, color_palette_index[], MAX_BMP_SIZE(bmp.bm_w, bmp.bm_h) + 30000);
		571
		572	const std::size_t pointer_offset = rle_big ? 4 + 2 * bmp.bm_h : 4 + bmp.bm_h;
		573	auto ptr = &bmp.get_bitmap_data()[pointer_offset];
		574	auto ptr2 = &temp[pointer_offset];
		575	for (int i = 0; i < bmp.bm_h; i++) {
		576	auto start = ptr2;
		577	if (rle_big)
		578	line_size = GET_INTEL_SHORT(&bmp.get_bitmap_data()[4 + 2 * i]);
		579	else
		580	line_size = bmp.get_bitmap_data()[4 + i];
		581	for (int j = 0; j < line_size; j++) {
		582	const uint8_t v = ptr[j];
		583	if (!IS_RLE_CODE(v))
		584	{
		585	if (IS_RLE_CODE(colormap[v]))
		586	*ptr2++ = color_palette_index{RLE_CODE \| 1}; // add "escape sequence"
		587	*ptr2++ = colormap[v]; // translate
		588	} else {
		589	*ptr2++ = ptr[j]; // just copy current rle code
		590	if ((ptr[j] & NOT_RLE_CODE) == 0)
		591	break;
		592	j++;
		593	*ptr2++ = colormap[ptr[j]]; // translate
		594	}
		595	}
		596	if (rle_big) // set line size
		597	PUT_INTEL_SHORT(&temp[4 + 2 * i], static_cast<uint16_t>(ptr2 - start));
		598	else
		599	temp[4 + i] = ptr2 - start;
		600	ptr += line_size; // go to next line
		601	}
		602	len = ptr2 - temp.get();
		603	memcpy(bmp.get_bitmap_data(), &len, 4);
		604	memcpy(&bmp.get_bitmap_data()[4], &temp.get()[4], len - 4);
		605	}
		606
		607	void bm_rle_src_stride::advance_src_bits()
		608	{
		609	/* Both bytes are always legal to read since the bitmap data
		610	* is placed after the length table. Reading both, then
		611	* conditionally masking out the high bits (dependent on
		612	* BM_FLAG_RLE_BIG) encourages the compiler to implement
		613	* this line without using branches.
		614	*/
		615	const uintptr_t u = (ptr_src_bit_lengths[0] \| (static_cast<uintptr_t>(ptr_src_bit_lengths[1]) << 8)) & src_bit_load_mask;
		616	ptr_src_bit_lengths += src_bit_stride_size;
		617	src_bits += u;
		618	}
		619
		620	bm_rle_expand::step_result bm_rle_expand::step_internal(uint8_t const begin_dbits, uint8_t const end_dbits)
		621	{
		622	const auto rd = gr_rle_decode(src_bits, begin_dbits, {end_src_bm, end_dbits});
		623	/* If the destination buffer is exhausted, return without
		624	* modifying the source state. This lets the caller retry
		625	* with a larger buffer, if desired.
		626	*/
		627	if (unlikely(begin_dbits == rd))
		628	return dst_exhausted;
		629	advance_src_bits();
		630	return again;
		631	}
		632
		633	}

Subversion Repositories Games.Descent

Games.Descent /common/2d/rle.cpp – Rev 1