/*
								+--------------------------------+
								|                                |
								|   ***  Bitmap font tool  ***   |
								|                                |
								|  Copyright © -tHE SWINe- 2010  |
								|                                |
								|        FontTexture2.cpp        |
								|                                |
								+--------------------------------+
*/

/**
 *	@file FontTexture2.cpp
 *	@author -tHE SWINe-
 *	@brief a simple bitmap font texture creation tool
 *	@date 2010
 */

#include "NewFix.h"
#include "CallStack.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include "Vector.h"
#include "MinMax.h"
#include "Tga.h"
#include "Timer.h"
#include "UniConv.h"
#include "Unused.h"
#include "Crc.h"
//#include "Dir.h" // not required (?)
#include "UniBlocks.h"
#include "BinPacking.h"
#include "FontTexture2.h"
#include "StlUtils.h"

using namespace bitmapfont2;
// some objects are contained in this particular namespace to avoid
// polluting the global namespace with overly generic names

#if defined(_WIN32) || defined(_WIN64)

//#define WIN32_LEAN_AND_MEAN // unicode?
#include <windows.h>

#ifndef CLEARTYPE_QUALITY
#define CLEARTYPE_QUALITY 5
#endif // CLEARTYPE_QUALITY
#ifndef CLEARTYPE_COMPAT_QUALITY
#define CLEARTYPE_COMPAT_QUALITY 6
#endif // CLEARTYPE_COMPAT_QUALITY

/**
 *	@brief a simple class for rasterizing glyphs of a given font
 */
class bitmapfont2::CGlyphRenderer {
public:
	/**
	 *	@copydoc CBitmapFont::TRectangle
	 */
	typedef CBitmapFont::TRectangle TRectangle;

	/**
	 *	@brief GDI bitmap
	 */
	class CGDI_Bitmap {
	private:
		int m_n_width;
		int m_n_height;
		int m_n_plane_num;
		int m_n_bit_count;
		unsigned char *m_p_buffer;
		BITMAPINFO m_t_info;
		HBITMAP m_h_dib;

		HDC m_h_dc; // dc for rendering to bitmap
		HGDIOBJ m_h_prev_dc_obj;

	public:
		/**
		 *	@brief default constructor
		 *
		 *	Creates bitmap with size n_width per n_height pixels,
		 *		n_plane_num color planes and n_bit_count bits per pixel
		 *
		 *	@param[in] n_width is bitmap width in pixels
		 *	@param[in] n_height is bitmap height in pixels
		 *	@param[in] n_plane_num is number of bit planes (should be 1)
		 *	@param[in] n_bit_count is number of bits per pixel (should be 32)
		 *
		 *	@note Uncompressed RGB formats are supported only.
		 */
		CGDI_Bitmap(int n_width, int n_height, int n_plane_num = 1, int n_bit_count = 32)
			:m_n_width(n_width), m_n_height(n_height),
			m_n_plane_num(n_plane_num), m_n_bit_count(n_bit_count), m_h_dib(0), m_h_dc(0)
		{
			int n_image_size = n_width * n_height * n_plane_num * ((n_bit_count + 7) / 8);

			m_t_info.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
			m_t_info.bmiHeader.biWidth = n_width;
			m_t_info.bmiHeader.biHeight = n_height;
			m_t_info.bmiHeader.biPlanes = n_plane_num;
			m_t_info.bmiHeader.biBitCount = n_bit_count;
			m_t_info.bmiHeader.biCompression = BI_RGB;
			m_t_info.bmiHeader.biSizeImage = 0;//n_image_size;
			m_t_info.bmiHeader.biXPelsPerMeter = 72;
			m_t_info.bmiHeader.biYPelsPerMeter = 72;
			m_t_info.bmiHeader.biClrUsed = 0;
			m_t_info.bmiHeader.biClrImportant = 0;
			// fill bitmap info header

			if(!(m_p_buffer = new(std::nothrow) unsigned char[n_image_size]))
				return;
			// alloc bitmap buffer

			m_h_dib = CreateDIBSection(NULL, &m_t_info, DIB_RGB_COLORS,
				(void**)&m_p_buffer, NULL, 0);
			// create dib
		}

		/**
		 *	@brief destructor
		 */
		~CGDI_Bitmap()
		{
			if(m_h_dib) {
				ReleaseDC();
				DeleteObject(m_h_dib);
			}
		}

		/**
		 *	@brief checks if constructor succeeded
		 *	@return In case constructor succeeded in creating bitmap, returns true. otherwise false.
		 */
		inline bool b_Status() const
		{
			return m_h_dib != 0;
		}

		/**
		 *	@brief gets bitmap width
		 *	@return Returns bitmap width.
		 */
		inline int n_Width() const { return m_n_width; }

		/**
		 *	@brief gets bitmap height
		 *	@return Returns bitmap height.
		 */
		inline int n_Height() const { return m_n_height; }

		/**
		 *	@brief gets bitmap buffer
		 *	@return Returns pointer to bitmap buffer (do not delete!).
		 */
		inline unsigned char *p_Buffer() { return m_p_buffer; }

		/**
		 *	@brief gets bitmap buffer
		 *	@return Returns const pointer to bitmap buffer (do not delete!).
		 */
		inline const unsigned char *p_Buffer() const { return m_p_buffer; }

		/**
		 *	@brief gets bitmap DC
		 *
		 *	Use to render to bitmap. Creates device context and assigns this bitmap to it.
		 *
		 *	@return Returns device context of the bitmap.
		 *	@note Don't forget to release DC by calling ReleaseDC() once rendering
		 *		is finished.
		 */
		HDC h_GetDC()
		{
			if(m_h_dc)
				return m_h_dc;
			if(!(m_h_dc = CreateCompatibleDC(0)/*CreateDC("DISPLAY", NULL, NULL, NULL)*/))
				return 0;
			m_h_prev_dc_obj = SelectObject(m_h_dc, m_h_dib);
			return m_h_dc;
		}

		/**
		 *	@brief releases device context
		 *
		 *	This should be called once device context obtained by calling h_GetDC() is no longer needed.
		 *
		 *	@return Returns true on success or in case no context was created, otherwise false.
		 */
		bool ReleaseDC()
		{
			if(!m_h_dc)
				return true;
			SelectObject(m_h_dc, m_h_prev_dc_obj);
			bool b_result = DeleteDC(m_h_dc) != FALSE;
			m_h_dc = 0;

			return b_result;
		}
	};

	/**
	 *	@brief a simple utility for loading fonts from files on win32
	 */
	class CFontResourceLoader {
	public:
		/**
		 *	@brief loads a font from a file (windows only)
		 *
		 *	@param[in] p_s_filename is file name
		 *	@param[out] r_s_font_faces is filled with list of loaded font face names
		 *
		 *	@return Returns number of fonts loaded on success, or -1 on failure.
		 *
		 *	@note The font is loaded for the process, and should be later
		 *		deleted using Unload_FontFile().
		 *	@note In case (a portion of) the font was already in the system, the font
		 *		face list will not contain the faces that were loaded but already present.
		 */
		static int n_Load_FontFile(const char *p_s_filename, std::vector<std::string> &r_s_font_faces)
		{
			r_s_font_faces.clear();
			// ...

			int n_new_font_num;
			std::vector<std::string> font_list, font_list2;
			{
				CGDI_Bitmap bitmap(32, 32);
				HDC h_dc = bitmap.h_GetDC();
				if(!EnumFontFamiliesA(h_dc, NULL, &EnumFontFamExProc, (LPARAM)&font_list))
					return -1;
				if(!(n_new_font_num = AddFontResourceExA(p_s_filename, FR_PRIVATE, 0)))
					return -1;
				if(!EnumFontFamiliesA(h_dc, NULL, &EnumFontFamExProc, (LPARAM)&font_list2)) {
					Unload_FontFile(p_s_filename); // !!
					return -1;
				}
				bitmap.ReleaseDC(); // not neccessary, destructor would do that
			}
			// load the resource, get list of fonts before and after

			std::sort(font_list.begin(), font_list.end());
			font_list.erase(std::unique(font_list.begin(), font_list.end()), font_list.end());
			std::sort(font_list2.begin(), font_list2.end());
			font_list2.erase(std::unique(font_list2.begin(), font_list2.end()), font_list2.end());
			// sort the names (std::set_difference requires the sets to be sorted), unique when at it

			try {
				std::insert_iterator<std::vector<std::string> > it(r_s_font_faces, r_s_font_faces.begin());
				std::set_difference(font_list2.begin(), font_list2.end(),
					font_list.begin(), font_list.end(), it);
			} catch(std::bad_alloc&) {
				Unload_FontFile(p_s_filename); // !!
				return -1;
			}
			// find differences in the lists to see which fonts were loaded

			return n_new_font_num;
		}

		/**
		 *	@brief unloads a font, previously loaded using n_Load_FontFile()
		 *	@param[in] p_s_filename is file name
		 */
		static void Unload_FontFile(const char *p_s_filename)
		{
			RemoveFontResourceExA(p_s_filename, FR_PRIVATE, 0);
		}

	protected:
		static int CALLBACK EnumFontFamExProc(const LOGFONTA *lpelfe,
			const TEXTMETRICA *lpntme, DWORD FontType, LPARAM lParam) // throw()
		{
			std::vector<std::string> &font_list = *(std::vector<std::string>*)lParam; // get list
			return stl_ut::Resize_Add_1More(font_list) &&
				stl_ut::AssignCStr(font_list.back(), lpelfe->lfFaceName);
		}
	};

protected:
	CGDI_Bitmap *m_p_bitmap;
	HFONT m_h_font;

	// basic glyph metrics
	int n_ascent;
	int n_descent;
	int n_height;
	int n_int_leading;
	int n_ext_leading;

	int n_space_width; // width of the space glyph (it is not stored physically)
	int n_x_height; // height of the 'x' glyph

	int n_newline_height; // newline height (distance the caret must shift on newline); this equals n_height + n_ext_leading

	const char *m_p_s_filename;

public:
	CGlyphRenderer(const char *p_s_font_face = "arial", int n_font_size = 30,
		int n_font_weight = 400, bool b_italic = false, bool b_underline = false,
		bool b_use_cleartype = true)
		:m_p_bitmap(0), m_p_s_filename(0)
	{
#ifdef __FONT_TEXTURE_WINDOWS_AUTOLOAD_FONTS_FROM_FILE
		std::vector<std::string> s_name_list; // must be in scope for duration of this function
		if(strchr(p_s_font_face, '.') != 0) { // .ttf or .otf, or whatever
			FILE *p_fr; // do not want to force inclusion of Dir.cpp / .h, just try to open it
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400
			if(!fopen_s(&p_fr, p_s_font_face, "rb")) {
#else //_MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
			if((p_fr = fopen(p_s_font_face, "rb"))) {
#endif //_MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
				fclose(p_fr);
				// font face is in fact a filename

				int n_face_num = CFontResourceLoader::n_Load_FontFile(p_s_font_face, s_name_list);
				if(n_face_num != 1 || s_name_list.size() != 1) { // n_face_num != 1 might backfire, not sure how it works
					CFontResourceLoader::Unload_FontFile(p_s_font_face);
					// not clear which font(s) were loaded, which is to be used

					m_p_bitmap = 0; // to mark error
					return;
				} else {
					if(!(m_p_s_filename = _strdup(p_s_font_face))) {
						CFontResourceLoader::Unload_FontFile(p_s_font_face);
						// fail - not enough memory, would not be able to properly free the font later

						m_p_bitmap = 0; // to mark error
						return;
					} else
						p_s_font_face = s_name_list.front().c_str();
					// use the loaded face
				}
			}
		}
#endif // __FONT_TEXTURE_WINDOWS_AUTOLOAD_FONTS_FROM_FILE

		LOGFONTA t_logfont = {0};
		t_logfont.lfHeight = -n_font_size;
		t_logfont.lfWidth = 0;
#ifdef __BITMAP_FONT_GDI_FONT_ESCAPEMENT_HACK
		t_logfont.lfEscapement = 1; // hack - this fixes some glyphs being clipped (a GDI bug?). this also causes 0.1 degree rotation. // @todo - remove this and find out why does TextOut() crop the glyphs
#else // __BITMAP_FONT_GDI_FONT_ESCAPEMENT_HACK
		t_logfont.lfEscapement = 0;
#endif // __BITMAP_FONT_GDI_FONT_ESCAPEMENT_HACK
		t_logfont.lfOrientation = 0;
		t_logfont.lfWeight = n_font_weight;
		t_logfont.lfItalic = (b_italic)? TRUE : FALSE;
		t_logfont.lfUnderline = (b_underline)? TRUE : FALSE;
		t_logfont.lfStrikeOut = FALSE;
		t_logfont.lfCharSet = DEFAULT_CHARSET; //OEM_CHARSET; // DEFAULT_CHARSET seems to work better to get chinese
		t_logfont.lfOutPrecision = OUT_TT_PRECIS;
		t_logfont.lfClipPrecision = CLIP_DEFAULT_PRECIS;
		t_logfont.lfQuality = (b_use_cleartype)? CLEARTYPE_QUALITY : ANTIALIASED_QUALITY;
		t_logfont.lfPitchAndFamily = DEFAULT_PITCH;
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400
		strncpy_s(t_logfont.lfFaceName, sizeof(t_logfont.lfFaceName),
			p_s_font_face, sizeof(t_logfont.lfFaceName) - 1);
#else //_MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
		strncpy(t_logfont.lfFaceName, p_s_font_face, sizeof(t_logfont.lfFaceName));
#endif //_MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
		t_logfont.lfFaceName[sizeof(t_logfont.lfFaceName) /
			sizeof(t_logfont.lfFaceName[0]) - 1] = 0; // ...
		// fill LOGFONT

		if(!(m_h_font = CreateFontIndirectA(&t_logfont)))
			return;
		// create the font

		if(!(m_p_bitmap = new(std::nothrow) CGDI_Bitmap(64, 64)))
			return;
		if(!m_p_bitmap->b_Status()) {
			delete m_p_bitmap;
			m_p_bitmap = 0; // to mark error
			return;
		}
		// create the bitmap

		{
			HDC h_dc = m_p_bitmap->h_GetDC();
			HGDIOBJ h_prev_font = SelectObject(h_dc, m_h_font);
			// set font in the bitmap

			TEXTMETRIC t_text_metric;
			GetTextMetrics(h_dc, &t_text_metric);
			n_ascent = t_text_metric.tmAscent;
			n_descent = -t_text_metric.tmDescent;
			n_height = t_text_metric.tmHeight;
			n_int_leading = t_text_metric.tmInternalLeading;
			n_ext_leading = t_text_metric.tmExternalLeading;
			// read text metrics

			n_newline_height = t_text_metric.tmHeight + t_text_metric.tmExternalLeading;
			// newline height (which is composite, maybe this dosn't need to be stored)

			SIZE t_size;
			GetTextExtentPoint32A(h_dc, " ", 1, &t_size);
			//n_height = t_size.cy; // matches t_text_metric.tmHeight (or at least for verdana it does)
			n_space_width = t_size.cx;
			// space width

			GetTextExtentPoint32A(h_dc, "x", 1, &t_size);
			n_x_height = t_size.cy;
			// 'x' height

			SelectObject(h_dc, h_prev_font);
			m_p_bitmap->ReleaseDC();
			// cleanup bitmap and font
		}
		// get some font info ...
	}

	~CGlyphRenderer()
	{
		if(m_p_bitmap)
			delete m_p_bitmap;
		if(m_h_font)
			DeleteObject(m_h_font);
		if(m_p_s_filename) {
			free((void*)m_p_s_filename); // allocated by strdup()
			CFontResourceLoader::Unload_FontFile(m_p_s_filename); // don't leave it loaded
		}
	}

	bool b_Status() const
	{
		return m_p_bitmap && m_h_font;
	}

	void Get_FontMetrics(TFontInfo &r_t_font_info) const
	{
		r_t_font_info.n_ascent = n_ascent;
		r_t_font_info.n_descent = n_descent;
		r_t_font_info.n_height = n_height;
		r_t_font_info.n_int_leading = n_int_leading;
		r_t_font_info.n_ext_leading = n_ext_leading;
		r_t_font_info.n_space_width = n_space_width;
		r_t_font_info.n_x_height = n_x_height;
		r_t_font_info.n_newline_height = n_newline_height;
	}

	bool RenderGlyph(int n_utf32, TGlyphInfo &r_t_info, TRectangle &r_t_raster_info)
	{
		wchar_t p_s_text[3];
		if(n_utf32 < 0x010000) {
			if(n_utf32 >= 0xd800 && n_utf32 <= 0xdfff)
				return false;
			// non-characters

			p_s_text[0] = wchar_t(n_utf32);
			p_s_text[1] = 0;
		} else {
			if(n_utf32 > 0x10ffff)
				return false;
			// too high

			int n_utf32_lower = n_utf32 - 0x10000;
			p_s_text[0] = wchar_t(0xd800 + (n_utf32_lower >> 10));
			p_s_text[1] = wchar_t(0xdc00 + (n_utf32_lower & 0x3ff));
			p_s_text[2] = 0;
			// encode as surrogate pair (fixme - do windows support that?)
		}
		// encode utf-32 to utf-16 null-terminated string

		//memset(m_p_bitmap->p_Buffer(), 0, m_p_bitmap->n_Width() *
		//	m_p_bitmap->n_Height() * sizeof(uint32_t)); // ETO_OPAQUE does that
		// clear the bitmap

		const int n_min_clearance = max(32, n_height);
		// minimal clearance in the bitmap

		int n_caret_shift; // amounts to horizontal glyph size
		int n_y_offset; // position of the glyph baseline
		int n_off_x, n_off_y; // coordinate where was the glyph rendered (points to the baseline)
		int n_min_x, n_max_x;
		int n_min_y, n_max_y; // rectangle in the bitmap
		for(;;) {
			HDC h_dc = m_p_bitmap->h_GetDC();
			//SetBkMode(h_dc, TRANSPARENT);
			SetBkColor(h_dc, 0);
			SetTextColor(h_dc, 0xffffff);
			HGDIOBJ h_prev_font = SelectObject(h_dc, m_h_font);
			// get dc, select font

			SIZE t_size;
			GetTextExtentPoint32W(h_dc, p_s_text, wcslen(p_s_text), &t_size);
			n_caret_shift = t_size.cx;
			/*ABC t_abc;
			GetCharABCWidths(h_dc, n_utf32, n_utf32, &t_abc);
			n_caret_shift = t_abc.abcB + t_abc.abcA;*/ // does not work for unicode
			// get glyph size

			TEXTMETRIC t_text_metric;
			GetTextMetrics(h_dc, &t_text_metric);
			n_y_offset = -t_text_metric.tmDescent + t_text_metric.tmHeight;
			// get glyph y-offset

			n_off_x = m_p_bitmap->n_Width() / 2;
			n_off_y = -m_p_bitmap->n_Height() / 2;
			//TextOutW(h_dc, n_off_x, m_p_bitmap->n_Height() + n_off_y, p_s_text, wcslen(p_s_text));
			RECT t_rect;
			t_rect.top = 0;
			t_rect.left = 0;
			t_rect.right = m_p_bitmap->n_Width();
			t_rect.bottom = m_p_bitmap->n_Height();
			ExtTextOutW(h_dc, n_off_x, m_p_bitmap->n_Height() + n_off_y,
				ETO_OPAQUE, &t_rect, p_s_text, wcslen(p_s_text), NULL);
			// render the glyph in the middle

			const uint32_t *p_buffer = (const uint32_t*)m_p_bitmap->p_Buffer();
			// get buffer

			n_min_x = m_p_bitmap->n_Width();
			n_max_x = 0;
			int n_hit_position = 0;
			for(int n_x = 0; n_x < m_p_bitmap->n_Width(); ++ n_x) {
				if(!b_Column_Empty(n_hit_position, p_buffer + n_x, m_p_bitmap->n_Height(), m_p_bitmap->n_Width())) {
					if(n_min_x > n_x)
						n_min_x = n_x;
					if(n_max_x < n_x)
						n_max_x = n_x;
				}
			}
			n_min_y = m_p_bitmap->n_Height();
			n_max_y = 0;
			int n_char_w = n_max_x - n_min_x + 1;
			if(n_char_w > 0) {
				int n_hit_position = 0;
				for(int n_y = 0; n_y < m_p_bitmap->n_Height(); ++ n_y) {
					if(!b_Scanline_Empty(n_hit_position, p_buffer + n_min_x + n_y * m_p_bitmap->n_Width(), n_char_w)) {
						if(n_min_y > n_y)
							n_min_y = n_y;
						if(n_max_y < n_y)
							n_max_y = n_y;
					}
				}
			}
			// get glyph bitmap dimensions (glyph metrics are no good for this)

			SelectObject(h_dc, h_prev_font);
			m_p_bitmap->ReleaseDC();
			// release dc

			bool b_failed_horz_clearance = n_min_x <= n_min_clearance ||
				n_max_x >= m_p_bitmap->n_Width() - n_min_clearance;
			bool b_failed_vert_clearance = n_min_y <= n_min_clearance ||
				n_max_y >= m_p_bitmap->n_Height() - n_min_clearance;
			if(b_failed_horz_clearance || b_failed_vert_clearance) {
				// the clearance is too low, a bigger bitmap is needed

				CGDI_Bitmap *p_new_bitmap;
				if(!(p_new_bitmap = new(std::nothrow) CGDI_Bitmap((b_failed_horz_clearance)?
				   m_p_bitmap->n_Width() * 2 : m_p_bitmap->n_Width(), (b_failed_vert_clearance)?
				   m_p_bitmap->n_Height() * 2 : m_p_bitmap->n_Height())))
					return false;
				if(!p_new_bitmap->b_Status()) {
					delete p_new_bitmap;
					return false;
				}
				// create the new bitmap

				delete m_p_bitmap;
				m_p_bitmap = p_new_bitmap;
				// replace the old bitmap

				continue;
				// try again
			} else
				break; // happy
			// decide whether the glyph was rendered with sufficient clearance
		}

		if(n_min_x > n_max_x || n_min_y > n_max_y) {
			n_min_x = 0;
			n_max_x = 0;
			n_min_y = 0;
			n_max_y = 0;
		}
		// handle unrenderable glyphs

		{
			TGlyphInfo t_info = {0};
			t_info.n_code = n_utf32;
			t_info.n_bitmap_width = n_max_x - n_min_x + 1;
			t_info.n_bitmap_height = n_max_y - n_min_y + 1;
			t_info.n_baseline_offset_x = n_min_x - n_off_x;
			t_info.n_baseline_offset_y = n_min_y + n_off_y + n_y_offset;
			t_info.n_caret_shift = n_caret_shift;
			// fill glyph 

			/*t_info.b_rotation = false;
			t_info.n_bitmap_pos_x = 0;
			t_info.n_bitmap_pos_y = 0;*/
			// this is up to bin packer to fill (this is here just to avoid rubish)

			r_t_info = t_info;
		}
		// output glyph info (didn't write directly here so "t_info = {0};" was possible)

		r_t_raster_info.n_left = n_min_x;
		r_t_raster_info.n_top = n_min_y;
		r_t_raster_info.n_width = n_max_x - n_min_x + 1;
		r_t_raster_info.n_height = n_max_y - n_min_y + 1;
		// output raster info

		return true;
	}

	void Copy_Raster(uint32_t *p_dest, size_t n_scanline_width, int n_orientation, TRectangle t_raster_info)
	{
		_ASSERTE(t_raster_info.n_left < unsigned(m_p_bitmap->n_Width()));
		_ASSERTE(t_raster_info.n_top < unsigned(m_p_bitmap->n_Height()));
		_ASSERTE(t_raster_info.n_left + t_raster_info.n_width <= unsigned(m_p_bitmap->n_Width()));
		_ASSERTE(t_raster_info.n_top + t_raster_info.n_height <= unsigned(m_p_bitmap->n_Height()));

		const uint32_t *p_buffer = (const uint32_t*)m_p_bitmap->p_Buffer();
		// get buffer

		size_t n_bitmap_width = m_p_bitmap->n_Width();
		p_buffer += t_raster_info.n_left + t_raster_info.n_top * n_bitmap_width;
		// skip to the first pixel of the last scanline

		if(!n_orientation) {
			p_buffer += (t_raster_info.n_height - 1) * n_bitmap_width;
			// y-flip

			for(size_t y = 0; y < t_raster_info.n_height; ++ y,
			   p_buffer -= n_bitmap_width, p_dest += n_scanline_width) {
				const uint32_t *p_src_scan_ptr = p_buffer;
				uint32_t *p_dest_scan_ptr = p_dest;
				for(size_t x = 0; x < t_raster_info.n_width; ++ x, ++ p_src_scan_ptr, ++ p_dest_scan_ptr) {
					uint32_t n_src_color = *p_src_scan_ptr;
					// get source pixel

					uint32_t n_gray = ((n_src_color >> 16) & 0xff) * 2;
					n_gray += ((n_src_color >> 8) & 0xff) * 5;
					n_gray += (n_src_color & 0xff) * 1;
					n_gray /= 8;
					// convert to greyscale (if using cleartype, edges will be coloured)

					*p_dest_scan_ptr = 0xff000000U | (n_gray << 16) | (n_gray << 8) | n_gray;
					// output the final color
				}
			}
		} else if(n_orientation == 1) { // 90 degrees CCW (top = left)
			p_buffer += (t_raster_info.n_height - 1) * n_bitmap_width;
			// y-flip

			for(size_t y = 0; y < t_raster_info.n_height; ++ y, p_buffer -= n_bitmap_width) {
				const uint32_t *p_src_scan_ptr = p_buffer + t_raster_info.n_width - 1;
				for(size_t x = 0; x < t_raster_info.n_width; ++ x, -- p_src_scan_ptr) {
					uint32_t n_src_color = *p_src_scan_ptr;
					// get source pixel

					uint32_t n_gray = ((n_src_color >> 16) & 0xff) * 2;
					n_gray += ((n_src_color >> 8) & 0xff) * 5;
					n_gray += (n_src_color & 0xff) * 1;
					n_gray /= 8;
					// convert to greyscale (if using cleartype, edges will be coloured)

					p_dest[y + x * n_scanline_width] = 0xff000000U | (n_gray << 16) | (n_gray << 8) | n_gray;
					// output the final color
				}
			}
		} else if(n_orientation == 2) { // 180 degrees CCW (top = left)
			for(size_t y = 0; y < t_raster_info.n_height; ++ y, p_buffer += n_bitmap_width) {
				const uint32_t *p_src_scan_ptr = p_buffer + t_raster_info.n_width - 1;
				for(size_t x = 0; x < t_raster_info.n_width; ++ x, -- p_src_scan_ptr) {
					uint32_t n_src_color = *p_src_scan_ptr;
					// get source pixel

					uint32_t n_gray = ((n_src_color >> 16) & 0xff) * 2;
					n_gray += ((n_src_color >> 8) & 0xff) * 5;
					n_gray += (n_src_color & 0xff) * 1;
					n_gray /= 8;
					// convert to greyscale (if using cleartype, edges will be coloured)

					p_dest[x + y * n_scanline_width] = 0xff000000U | (n_gray << 16) | (n_gray << 8) | n_gray;
					// output the final color
				}
			}
		} else /*if(n_orientation == 3)*/ { // 270 degrees CCW (top = left)
			_ASSERTE(n_orientation == 3);
			for(size_t y = 0; y < t_raster_info.n_height; ++ y, p_buffer += n_bitmap_width) {
				const uint32_t *p_src_scan_ptr = p_buffer;
				for(size_t x = 0; x < t_raster_info.n_width; ++ x, ++ p_src_scan_ptr) {
					uint32_t n_src_color = *p_src_scan_ptr;
					// get source pixel

					uint32_t n_gray = ((n_src_color >> 16) & 0xff) * 2;
					n_gray += ((n_src_color >> 8) & 0xff) * 5;
					n_gray += (n_src_color & 0xff) * 1;
					n_gray /= 8;
					// convert to greyscale (if using cleartype, edges will be coloured)

					p_dest[y + x * n_scanline_width] = 0xff000000U | (n_gray << 16) | (n_gray << 8) | n_gray;
					// output the final color
				}
			}
		}
	}

private:
	CGlyphRenderer(const CGlyphRenderer &UNUSED(r_renderer)) {} // dont' use this to copy glyph renderers. use pointers if necessary
	CGlyphRenderer &operator =(const CGlyphRenderer &UNUSED(r_renderer)) { return *this; } // dont' use this to copy glyph renderers. use pointers if necessary

protected:
	static bool b_Scanline_Empty(int &r_n_hit_position, const uint32_t *p_buffer, int n_width)
	{
		_ASSERTE(r_n_hit_position >= 0 && r_n_hit_position < n_width);

		for(const uint32_t *p_buffer_ptr = p_buffer + r_n_hit_position, *p_end = p_buffer + n_width;
		   p_buffer_ptr != p_end; ++ p_buffer_ptr) {
			if(*p_buffer_ptr) {
				r_n_hit_position = p_buffer_ptr - p_buffer;
				return false;
			}
		}
		// investigate from the recent hit position onwards

		for(const uint32_t *p_buffer_ptr = p_buffer, *p_end = p_buffer + r_n_hit_position;
		   p_buffer_ptr != p_end; ++ p_buffer_ptr) {
			if(*p_buffer_ptr) {
				r_n_hit_position = p_buffer_ptr - p_buffer;
				return false;
			}
		}
		// investigate space left from the recent hit position

		return true;
	}

	static bool b_Column_Empty(int &r_n_hit_position, const uint32_t *p_buffer, int n_height, int n_width)
	{
		_ASSERTE(r_n_hit_position >= 0 && r_n_hit_position < n_height);

		for(const uint32_t *p_buffer_ptr = p_buffer + r_n_hit_position * n_width, *p_end = p_buffer + n_height * n_width;
		   p_buffer_ptr != p_end; p_buffer_ptr += n_width) {
			if(*p_buffer_ptr) {
				r_n_hit_position = (p_buffer_ptr - p_buffer) / n_width;
				return false;
			}
		}
		// investigate from the recent hit position onwards

		for(const uint32_t *p_buffer_ptr = p_buffer, *p_end = p_buffer + r_n_hit_position * n_width;
		   p_buffer_ptr != p_end; p_buffer_ptr += n_width) {
			if(*p_buffer_ptr) {
				r_n_hit_position = (p_buffer_ptr - p_buffer) / n_width;
				return false;
			}
		}
		// investigate space above the recent hit position

		return true;
	}
};

#else // _WIN32 || _WIN64

class bitmapfont2::CGlyphRenderer {
public:
	/**
	 *	@copydoc CBitmapFont::TRectangle
	 */
	typedef CBitmapFont::TRectangle TRectangle;

protected:
	// @todo - support freetype

public:
	CGlyphRenderer(const char *UNUSED(p_s_font_face) = "arial", int UNUSED(n_font_size) = 30,
		int UNUSED(n_font_weight) = 400, bool UNUSED(b_italic) = false,
		bool UNUSED(b_underline) = false, bool UNUSED(b_use_cleartype) = true)
	{
		// @todo
	}

	bool b_Status() const
	{
		fprintf(stderr, "error: FreeType not supported (yet)\n");
		return false; // @todo
	}
	
	void Get_FontMetrics(TFontInfo &r_t_font_info) const
	{
		fprintf(stderr, "error: FreeType not supported (yet)\n");
		/*r_t_font_info.n_ascent = n_ascent;
		r_t_font_info.n_descent = n_descent;
		r_t_font_info.n_height = n_height;
		r_t_font_info.n_int_leading = n_int_leading;
		r_t_font_info.n_ext_leading = n_ext_leading;
		r_t_font_info.n_space_width = n_space_width;
		r_t_font_info.n_x_height = n_x_height;
		r_t_font_info.n_newline_height = n_newline_height;*/
	}

	bool RenderGlyph(int UNUSED(n_utf32), TGlyphInfo &UNUSED(r_t_info),
		TRectangle &UNUSED(r_t_raster_info))
	{
		return false; // @todo
	}

	void Copy_Raster(uint32_t *UNUSED(p_dest), size_t UNUSED(n_scanline_width),
		int UNUSED(n_orientation), TRectangle UNUSED(t_raster_info))
	{
		// @todo
	}
};

#endif // _WIN32 || _WIN64

/*bool Debug_SaveGlyphImage(const char *p_s_filename, CGlyphRenderer &r_gr,
	int n_angle, CGlyphRenderer::TRectangle t_raster_info, const TBmp *p_skip_image = 0)
{
#if 0
	-- t_raster_info.n_left;
	-- t_raster_info.n_top;
	t_raster_info.n_width += 2;
	t_raster_info.n_height += 2;
#endif // 0
	// see one-pixel border arround the glyph

	TBmp t_bitmap;
	if(!Get_GlyphImage(t_bitmap, r_gr, n_angle, t_raster_info))
		return false;
	// get bitmap

	r_gr.Copy_Raster(t_bitmap.p_buffer, (n_angle & 1)?
		t_raster_info.n_height : t_bitmap.n_width, n_angle, t_raster_info);
	// copy raster

	if(p_skip_image) {
		if(t_bitmap.n_width == p_skip_image->n_width &&
		   t_bitmap.n_height == p_skip_image->n_height &&
		   !memcmp(t_bitmap.p_buffer, p_skip_image->p_buffer,
		   t_bitmap.n_width * t_bitmap.n_height * sizeof(uint32_t))) {
			delete[] t_bitmap.p_buffer;
			return true;
		}
		// won't work if angle != 0
	}
	// compare to skip-image

	bool b_result = CTgaCodec::Save_TGA(p_s_filename, t_bitmap);
	// save bitmap

	delete[] t_bitmap.p_buffer;
	// cleanup

	return b_result;
}*/

//#define __DEBUG_COLORS

/**
 *	@brief font metadata reader
 */
class CMetadataReader {
public:
	typedef CBitmapFont::CPage CPage;
	typedef std::list<CPage> CPageList;

protected:
	class CMetaBlockReader {
	protected:
		TBmp m_t_bmp; // don't really need to store reference, the buffer pointer is all that is needed
		TContainerInfo m_t_container_info;
		size_t m_n_size;
		size_t m_n_read_offset;

	public:
		CMetaBlockReader(const TBmp &r_t_bmp)
			:m_t_bmp(r_t_bmp), m_n_size(0), m_n_read_offset(0)
		{
			if(m_t_bmp.n_width < sizeof(uint32_t))
				return;
			// make sure the image is wide enough

			m_n_size = sizeof(TContainerInfo); // at least
			m_t_container_info.n_container_width = sizeof(uint32_t); // need this to calculate (x, y) position
			uint32_t n_container_width;
			if(n_Read(&n_container_width, sizeof(uint32_t)) != sizeof(uint32_t)) {
				m_n_size = 0;
				return;
			}
			m_t_container_info.n_container_width = n_container_width; // avoid reading directly into m_t_container_info
			if(m_t_container_info.n_container_width * m_t_bmp.n_height < sizeof(TContainerInfo)) {
				m_n_size = 0;
				return; // too narrow
			}
			// read container width

			m_n_read_offset = 0; // !!
			TContainerInfo t_container_info;
			if(n_Read(&t_container_info, sizeof(TContainerInfo)) != sizeof(TContainerInfo)) {
				m_n_size = 0; // to mark error
				return;
			}
			m_t_container_info = t_container_info; // avoid reading directly into m_t_container_info
			// read the container block

			if(m_t_container_info.n_container_width > unsigned(m_t_bmp.n_width) ||
			   m_t_container_info.n_container_height > unsigned(m_t_bmp.n_height)) {
				m_n_size = 0; // to mark error
				return;
			}
			// check container sanity

			m_n_size = m_t_container_info.n_container_width * m_t_container_info.n_container_height;
			// this is the upper bound
		}

		inline size_t n_Size() const
		{
			return m_n_size;
		}
		
		inline const TContainerInfo &t_ContainerInfo() const
		{
			return m_t_container_info;
		}

		size_t n_Skip(size_t n_size)
		{
			if(n_size > m_n_size || m_n_read_offset > m_n_size - n_size)
				return 0;
			// either skip all, or nothing

			m_n_read_offset += n_size;
			// skip

			return n_size;
		}

		size_t n_Read(void *p_data, size_t n_size)
		{
			if(n_size > m_n_size || m_n_read_offset > m_n_size - n_size)
				return 0;
			// either write all, or nothing

			uint8_t *p_data8 = (uint8_t*)p_data;
			for(size_t n_end = m_n_read_offset + n_size; m_n_read_offset < n_end; ++ m_n_read_offset, ++ p_data8) {
				size_t n_x = m_n_read_offset % m_t_container_info.n_container_width;
				size_t n_y = m_n_read_offset / m_t_container_info.n_container_width;
				*p_data8 = m_t_bmp.p_buffer[n_x + n_y * m_t_bmp.n_width] & 0xff;
			}
			// write the data to the block

			return n_size;
		}

		/**
		 *	@brief erases the data area in the bitmap
		 *	@param[in] n_blank_color is color of the blank area
		 */
		void Blank(uint32_t n_blank_color)
		{
			for(size_t y = 0; y < m_t_container_info.n_container_height; ++ y) {
				for(size_t x = 0; x < m_t_container_info.n_container_width; ++ x)
					m_t_bmp.p_buffer[x + y * m_t_bmp.n_width] = n_blank_color; // blank
			}
		}

		bool Finished(bool b_check_crc32 = true)
		{
			if(!b_check_crc32)
				return true;
			// nothing to do if CRC check disabled

			uint32_t n_crc32 = CCrc_32::n_Start();
			{
				TContainerInfo t_container_info_copy = m_t_container_info;
				t_container_info_copy.n_crc32 = 0;
				n_crc32 = CCrc_32::n_Crc(sizeof(TContainerInfo), &t_container_info_copy, n_crc32);
			}
			// hash the header itself, without the CRC value in it

			size_t n_end = m_n_read_offset;
			m_n_read_offset = sizeof(TContainerInfo); // skip the container, we already have that
			while(m_n_read_offset < n_end) {
				uint8_t n_byte;
				if(n_Read(&n_byte, sizeof(uint8_t)) != sizeof(uint8_t))
					return false;
				n_crc32 = CCrc_32::n_Crc(sizeof(uint8_t), &n_byte, n_crc32);
			}
			// calculate CRC of what was decoded

			n_crc32 = CCrc_32::n_Finalize(n_crc32);
			// finalize the CRC

			return n_crc32 == m_t_container_info.n_crc32;
			// the CRC's must match
		}
	};

	TFontInfo m_t_font_info;
	std::string m_s_font_face;
	std::vector<CPage::TItemType> m_glyph_list;
	std::list<CPage> m_page_list;
	std::vector<std::pair<size_t, size_t> > m_page_char_range_list;
	size_t m_n_page_num, m_n_current_page;
	uint32_t m_n_stream_id;
	TContainerInfo m_t_last_container;

public:
	CMetadataReader()
		:m_n_page_num(0), m_n_current_page(0)
	{}

	const std::list<CPage> &r_Page_List() const
	{
		return m_page_list;
	}

	const std::vector<CPage::TItemType> &r_Glyph_List() const
	{
		return m_glyph_list;
	}

	std::list<CPage> &r_Page_List()
	{
		return m_page_list;
	}

	std::vector<CPage::TItemType> &r_Glyph_List()
	{
		return m_glyph_list;
	}

	const TFontInfo &t_FontInfo() const
	{
		return m_t_font_info;
	}

	const char *p_s_FontFace() const
	{
		return m_s_font_face.c_str();
	}

	const TContainerInfo &t_Last_ContainerInfo() const
	{
		return m_t_last_container;
	}

	bool b_Complete() const
	{
		return m_n_page_num && m_n_current_page >= m_n_page_num &&
			m_n_current_page == m_page_list.size();
	}

	bool Blank(const TBmp &r_t_bitmap, uint32_t n_blank_color)
	{
		CMetaBlockReader reader(r_t_bitmap);
		if(!reader.n_Size())
			return false;
		// initialize metadata reader ...

		reader.Blank(n_blank_color);
		// blank the metadata area

		return true;
	}

	bool Read_Metadata(const TBmp &r_t_bitmap)
	{
		if(!m_n_page_num || m_n_current_page < m_n_page_num) {
			CMetaBlockReader reader(r_t_bitmap);
			if(!reader.n_Size())
				return false;
			// initialize metadata reader ...

			m_t_last_container = reader.t_ContainerInfo();
			if(!m_n_page_num) {
				m_n_page_num = m_t_last_container.n_block_num;
				m_n_stream_id = m_t_last_container.n_stream_id;
			} else {
				if(m_n_stream_id != m_t_last_container.n_stream_id)
					return false;
				// check stream id
			}
			// fill-in the number of blocks

			if(m_n_current_page != reader.t_ContainerInfo().n_block_id)
				return false;
			// the pages must be read in order

			if(!m_n_current_page) {
				if(reader.n_Read(&m_t_font_info, sizeof(TFontInfo)) != sizeof(TFontInfo))
					return false;
				// read font info

				if(!stl_ut::Resize_To_N(m_s_font_face, m_t_font_info.n_font_face_length) ||
				   reader.n_Read(&m_s_font_face[0], m_t_font_info.n_font_face_length * sizeof(char)) !=
				   m_t_font_info.n_font_face_length * sizeof(char))
					return false;
				// read font name

				for(size_t i = 0, n = m_t_font_info.n_extension_block_num; i < n; ++ i) {
					TExtensionBlock t_ext_block;
					if(reader.n_Read(&t_ext_block, sizeof(TExtensionBlock)) != sizeof(TExtensionBlock))
						return false;
					// read the extension block header

					bool b_decoded_block = false;
					switch(t_ext_block.n_block_id) {
					case 12345: // just to suppress the "switch statement contains no 'case' labels" warning
						// this case intentionally falls through
					default:
						if(t_ext_block.b_important)
							return false;
						// unknown extension block
						break; // skip compiler warning on android
					};
					// try to decode the block

					if(!b_decoded_block) {
						if(t_ext_block.b_important)
							return false;
						// failed to decode an important extension block

						if(reader.n_Skip(t_ext_block.n_payload_size) != t_ext_block.n_payload_size)
							return false;
						// skip over unimportant extension block palyoads
					}
					// just skip
				}
				// read extension blocks (currently it only skips
				// unimportant blocks, no extensions are supported)
			}
			// the first page contains font info

			if(m_n_current_page < m_n_page_num) {
				for(size_t i = 0, n = reader.t_ContainerInfo().n_page_info_num; i < n; ++ i) {
					TPageInfo t_pg_info;
					if(reader.n_Read(&t_pg_info, sizeof(TPageInfo)) != sizeof(TPageInfo))
						return false;
					//printf("page %d: %d glyphs to read\n", t_pg_info.n_page_id, t_pg_info.n_glyph_num); // debug
					// read the page info

					size_t n_current_glyph_num = m_glyph_list.size();
					if(!stl_ut::Resize_Add_NMore(m_glyph_list, t_pg_info.n_glyph_num) ||
					   reader.n_Read(&m_glyph_list[n_current_glyph_num], t_pg_info.n_glyph_num *
					   sizeof(TGlyphInfo)) != t_pg_info.n_glyph_num * sizeof(TGlyphInfo))
						return false;
					// read the glyphs into the global list

					if(t_pg_info.n_page_id + 1 == m_page_list.size()) {
						CPage &r_page = m_page_list.back();
						std::pair<size_t, size_t> &r_page_char_range = m_page_char_range_list.back();
						// the page is in the list, at it's tail (page 0 ~ size 1)

						if(r_page_char_range.second != n_current_glyph_num)
							return false;
						r_page_char_range.second = m_glyph_list.size();
						// just extend the range
					} else if(t_pg_info.n_page_id == m_page_list.size()) {
						try {
							if(t_pg_info.n_page_id == m_n_current_page) {
								m_page_list.push_back(CPage(r_t_bitmap.n_width, r_t_bitmap.n_height));
							} else {
								_ASSERTE(t_pg_info.n_page_id > m_n_current_page); // the page will come, it's resolution will be set later
								m_page_list.push_back(CPage(-1, -1));
							}
							// add a new page

							m_page_char_range_list.push_back(std::make_pair(n_current_glyph_num, m_glyph_list.size()));
							// add glyph range
						} catch(std::bad_alloc&) {
							return false;
						}
						// the page is not in the list, have to add it (page 0 ~ size 0)
					} else
						return false;
				}
				// read all the page info blocks
			}
			// read page info

			if(!reader.Finished())
				return false;
			// test CRC integrity

			if(m_n_current_page + 1 == m_n_page_num) {
				CPageList::iterator p_page_it = m_page_list.begin();
				for(size_t i = 0, n = m_page_list.size(); i < n; ++ i, ++ p_page_it) {
					CPage &r_page = *p_page_it;
					std::pair<size_t, size_t> &r_page_glyph_range = m_page_char_range_list[i];

					std::vector<TGlyphInfo*> &page_glyph_list = r_page.r_ItemList();
					page_glyph_list.resize(r_page_glyph_range.second - r_page_glyph_range.first);
					std::transform(m_glyph_list.begin() + r_page_glyph_range.first,
						m_glyph_list.begin() + r_page_glyph_range.second,
						page_glyph_list.begin(), p_MakeBoxPtr);
					// fill the list with pointers to the glyphs for this page
				}
			}
			// it was the last page: copy glyph pointers to CPages
		}
		// process pages containing metadata

		if(m_n_current_page < m_page_list.size()) {
			if(m_n_current_page + 1 == m_page_list.size()) {
				CPage &r_page = m_page_list.back();
				r_page.Set_Size(r_t_bitmap.n_width, r_t_bitmap.n_height);
				// the page is at the end of the list; set it's size
			} else {
				_ASSERTE(m_n_current_page < m_page_list.size());
				CPageList::iterator p_page_it = m_page_list.begin();
				for(size_t i = 0; i < m_n_current_page; ++ i)
					++ p_page_it;
				// find the current page

				CPage &r_page = *p_page_it;
				r_page.Set_Size(r_t_bitmap.n_width, r_t_bitmap.n_height);
				// set it's size
			}
		} else
			return false; // no glyph info for this page
		// update page resolution (not really useful)

		++ m_n_current_page;
		// increment the page counter

		return true;
	}

protected:
	static inline TGlyphInfo *p_MakeBoxPtr(TGlyphInfo &r_t_info)
	{
		return (TGlyphInfo*)&r_t_info;
	}
};

/**
 *	@brief font metadata writer
 */
class bitmapfont2::CMetadataWriter {
public:
	typedef CBitmapFontPage CPage;
	typedef std::list<CPage> CPageList;

protected:
	struct TBlockInfo {
		struct TGlyphRange {
			size_t n_page_index;
			const CPage *p_page;
			size_t n_first, n_last;

			inline TGlyphRange()
			{}

			inline TGlyphRange(size_t _n_page_index, const CPage *_p_page,
				size_t _n_first, size_t _n_last)
				:n_page_index(_n_page_index), p_page(_p_page),
				n_first(_n_first), n_last(_n_last)
			{}
		};
		std::vector<TGlyphRange> glyph_range_list;
	};
	std::vector<TBlockInfo> m_block_info_list;

	class CMetaBlockWriter {
	protected:
		TBmp m_t_bmp; // don't really need to store reference, the buffer pointer is all that is needed
		TContainerInfo m_t_container_info;
		size_t m_n_capacity;
		size_t m_n_write_offset;

	public:
		CMetaBlockWriter(TBmp &r_t_bmp, size_t n_block_id, size_t n_block_num,
			size_t n_container_width, size_t n_container_height, uint32_t n_stream_id,
			size_t n_page_info_num)
			:m_t_bmp(r_t_bmp), m_n_capacity(n_container_width * n_container_height),
			m_n_write_offset(sizeof(TContainerInfo))
		{
			_ASSERTE(n_block_id > 0); // need to use the other constructor for id = 0
			_ASSERTE(n_container_width <= unsigned(r_t_bmp.n_width));
			_ASSERTE(n_container_height <= unsigned(r_t_bmp.n_height));
			m_t_container_info.n_container_width = n_container_width;
			m_t_container_info.n_container_height = n_container_height;
			m_t_container_info.n_crc32 = CCrc_32::n_Start();
			m_t_container_info.n_stream_id = n_stream_id;
			m_t_container_info.n_block_id = n_block_id;
			m_t_container_info.n_block_num = n_block_num;
			m_t_container_info.n_page_info_num = n_page_info_num;
			// fill container info structure

			{
				TContainerInfo t_container_info_copy = m_t_container_info;
				t_container_info_copy.n_crc32 = 0;
				m_t_container_info.n_crc32 = CCrc_32::n_Crc(sizeof(TContainerInfo),
					&t_container_info_copy, m_t_container_info.n_crc32);
			}
			// hash the header itself, without the CRC value

#ifdef __DEBUG_COLORS
			Debug_Prefill();
#endif // __DEBUG_COLORS
		}

		CMetaBlockWriter(TBmp &r_t_bmp, size_t n_block_id, size_t n_block_num,
			size_t n_container_width, size_t n_container_height, uint32_t n_stream_id,
			TFontInfo t_font_info, const char *p_s_font_name, size_t n_page_info_num)
			:m_t_bmp(r_t_bmp), m_n_capacity(n_container_width * n_container_height),
			m_n_write_offset(sizeof(TContainerInfo))
		{
			_ASSERTE(n_block_id == 0); // need to use the other constructor for id > 0
			_ASSERTE(n_container_width <= unsigned(r_t_bmp.n_width));
			_ASSERTE(n_container_height <= unsigned(r_t_bmp.n_height));
			m_t_container_info.n_container_width = n_container_width;
			m_t_container_info.n_container_height = n_container_height;
			m_t_container_info.n_crc32 = CCrc_32::n_Start();
			m_t_container_info.n_stream_id = n_stream_id;
			m_t_container_info.n_block_id = n_block_id;
			m_t_container_info.n_block_num = n_block_num;
			m_t_container_info.n_page_info_num = n_page_info_num;
			// fill container info structure

			{
				TContainerInfo t_container_info_copy = m_t_container_info;
				t_container_info_copy.n_crc32 = 0;
				m_t_container_info.n_crc32 = CCrc_32::n_Crc(sizeof(TContainerInfo),
					&t_container_info_copy, m_t_container_info.n_crc32);
			}
			// hash the header itself, without the CRC value

			_ASSERTE(t_font_info.n_font_face_length == strlen(p_s_font_name)); // this must match
			n_Write(&t_font_info, sizeof(TFontInfo));
			n_Write(p_s_font_name, strlen(p_s_font_name) * sizeof(char));
			// write font info and font name

#ifdef __DEBUG_COLORS
			Debug_Prefill();
#endif // __DEBUG_COLORS
		}

		void Finalize()
		{
			//printf("DEBUG: finalized block: free space: %d B\n", m_n_capacity - m_n_write_offset); // debug

			m_t_container_info.n_crc32 = CCrc_32::n_Finalize(m_t_container_info.n_crc32);
			// finalize crc32

			m_n_write_offset = 0;
			TContainerInfo t_container_info_copy = m_t_container_info; // make a backup
			n_Write(&t_container_info_copy, sizeof(TContainerInfo)); // modifies CRC32 in m_t_container_info
			m_t_container_info = t_container_info_copy; // restore good CRC32
			// write container info block
		}

		size_t n_Write(const void *p_data, size_t n_size)
		{
			if(n_size > m_n_capacity || m_n_write_offset > m_n_capacity - n_size)
				return 0;
			// either write all, or nothing

			const uint8_t *p_data8 = (const uint8_t*)p_data;
			for(size_t n_end = m_n_write_offset + n_size; m_n_write_offset < n_end; ++ m_n_write_offset, ++ p_data8) {
				size_t n_x = m_n_write_offset % m_t_container_info.n_container_width;
				size_t n_y = m_n_write_offset / m_t_container_info.n_container_width;
				m_t_container_info.n_crc32 = CCrc_32::n_Crc(sizeof(uint8_t), p_data8, m_t_container_info.n_crc32);
				m_t_bmp.p_buffer[n_x + n_y * m_t_bmp.n_width] =
					0xff000000U | (*p_data8) | (*p_data8 << 8) | (*p_data8 << 16);
			}
			// write the data to the block

			return n_size;
		}

	protected:
#ifdef __DEBUG_COLORS
		void Debug_Prefill()
		{
			for(uint32_t y = 0; y < m_t_container_info.n_container_height; ++ y) {
				for(uint32_t x = 0; x < m_t_container_info.n_container_width; ++ x)
					m_t_bmp.p_buffer[x + y * m_t_bmp.n_width] = 0xff0000ffU;
			}
		}
#endif // __DEBUG_COLORS
	};

	const std::vector<TGlyphInfo> &m_r_glyph_info_list;
	const char *m_p_s_font_face;
	double m_f_glyphs_area;
	size_t m_n_page_size_padd;
	double m_f_free_page_area;
	//size_t m_n_max_page_num; // unused / useless
	size_t m_n_max_store_page_num;
	size_t m_n_container_block_num;
	size_t m_n_avg_container_block_area;
	size_t m_n_avg_container_block_width;
	size_t m_n_avg_container_block_height;
	size_t m_n_last_container_block_area;
	size_t m_n_last_container_block_width;
	size_t m_n_last_container_block_height;

	float m_f_worst_case_efficiency;
	size_t m_n_page_num_overestimate;
	size_t m_n_max_container_size;
	TFontInfo m_t_font_info;

	uint32_t m_n_stream_id;

	//size_t m_n_char_written; // debug

public:
	/**
	 *	@brief default constructor; estimates number of pages and layout of meta-blocks
	 *
	 *	@param[in] p_s_font_face is font face name (this is stored and need to be calculated with)
	 *	@param[in] t_font_info is font information (to be written to the infoblocks)
	 *	@param[in] n_page_size_padd
	 *	@param[in] r_glyph_info_list
	 *	@param[in] f_worst_case_efficiency is worst-case box-packing efficiency
	 */
	CMetadataWriter(const char *p_s_font_face, const TFontInfo &r_t_font_info,
		size_t n_page_size_padd, size_t n_max_container_size,
		const std::vector<TGlyphInfo> &r_glyph_info_list, double f_worst_case_efficiency = .85)
		:m_p_s_font_face(p_s_font_face), m_f_glyphs_area(0),
		m_n_page_size_padd(n_page_size_padd), m_r_glyph_info_list(r_glyph_info_list),
		m_f_worst_case_efficiency(float(f_worst_case_efficiency)), m_n_page_num_overestimate(0),
		m_n_max_container_size(n_max_container_size), m_t_font_info(r_t_font_info)
	{
		srand(int(time(NULL)));
		m_n_stream_id = (rand() & 0xffff) | ((rand() & 0xffff) << 16);
		// generate unique (random) stream id

		for(size_t i = 0, n = r_glyph_info_list.size(); i < n; ++ i) {
			m_f_glyphs_area += double(r_glyph_info_list[i].n_bitmap_width) *
				r_glyph_info_list[i].n_bitmap_height;
		}
		// sum up the area taken by the glyphs

		m_f_free_page_area = double(n_page_size_padd) * n_page_size_padd -
			double(n_max_container_size) * n_max_container_size; // free area on a page
		// this doesn't change

		Do_MetaInfoBlocks_Layout();
	}

	/**
	 *	@brief gets maximal number of pages that fit the allocated storage
	 *	@return Returns maximal number of pages that fit the allocated storage.
	 */
	inline size_t n_MaxStorage_Page_Num() const
	{
		return m_n_max_store_page_num;
	}

	/**
	 *	@brief increases extimate of the number of pages
	 *	@param[in] n_extra_page_num is (cummulative) estimate correction
	 */
	void Increase_PageEstimate(size_t n_extra_page_num)
	{
		m_n_page_num_overestimate += n_extra_page_num;
		Do_MetaInfoBlocks_Layout();
	}

	/**
	 *	@brief gets number of metadata blocks
	 *	@return Returns number of metadata blocks.
	 */
	inline size_t n_MetaBlock_Num() const
	{
		return m_n_container_block_num;
	}

	/**
	 *	@brief gets metadata block width
	 *	@param[in] n_index is zero-based metadata block index (must be less than n_MetaBlock_Num())
	 *	@return Returns width of the selected block.
	 */
	inline size_t n_MetaBlock_Width(size_t n_index) const
	{
		return (n_index + 1 < m_n_container_block_num)?
			m_n_avg_container_block_width : m_n_last_container_block_width;
	}

	/**
	 *	@brief gets metadata block height
	 *	@param[in] n_index is zero-based metadata block index (must be less than n_MetaBlock_Num())
	 *	@return Returns height of the selected block.
	 */
	inline size_t n_MetaBlock_Height(size_t n_index) const
	{
		return (n_index + 1 < m_n_container_block_num)?
			m_n_avg_container_block_height : m_n_last_container_block_height;
	}

	/**
	 *	@brief gets metadata block area
	 *	@param[in] n_index is zero-based metadata block index (must be less than n_MetaBlock_Num())
	 *	@return Returns area of the selected block.
	 */
	inline size_t n_MetaBlock_Area(size_t n_index) const
	{
		return (n_index + 1 < m_n_container_block_num)?
			m_n_avg_container_block_area : m_n_last_container_block_area;
	}

	void Update_FontInfo(TFontInfo &r_t_font_info)
	{
		_ASSERTE(m_t_font_info.n_font_face_length == r_t_font_info.n_font_face_length);
		m_t_font_info = r_t_font_info;
	}

	/**
	 *	@brief prepares the final layout of metadata blocks and their contents
	 *	@param[in] r_page_list is list of allocated pages
	 */
	bool Prepare_PageMeta_Layout(CPageList &r_page_list)
	{
		_ASSERTE(r_page_list.size() <= m_n_max_store_page_num);
		// make sure all the metainfo blocks do fit

		CPageList::const_iterator p_page_it = r_page_list.begin(), p_end_it = r_page_list.end();
		size_t n_current_page = 0, n_current_glyph = 0;
		// page and glyph iterators

		for(size_t n_block = 0; n_block < m_n_container_block_num; ++ n_block) {
			size_t n_block_size = n_MetaBlock_Area(n_block);
			// calculate the block size

			_ASSERTE(n_block_size > n_Block_HeaderSize(!n_block));
			size_t n_block_space = n_block_size - n_Block_HeaderSize(!n_block);
			// calculate block space that remains for pages and glyphs

			/*printf("DEBUG: block %d : %d x %d (free space " PRIsizeB "B)\n", n_block,
				n_MetaBlock_Width(n_block), n_MetaBlock_Height(n_block),
				PRIsizeBparams(n_block_space));*/ // debug

			TBlockInfo t_block_info;
			//size_t n_glyph_info_num = 0; // debug

			if(p_page_it != p_end_it) {
				while(n_block_space >= sizeof(TPageInfo) + sizeof(TGlyphInfo)) {
					const CPage &r_page = *p_page_it;
					// get the current page

					const std::vector<TGlyphInfo*> &r_glyph_list = r_page.r_ItemList();
					// get the list of glyphs in the current page

					size_t n_remaining_glyphs = r_glyph_list.size() - n_current_glyph;
					size_t n_write_glyph_num = (n_block_space - sizeof(TPageInfo)) /
						sizeof(TGlyphInfo);
					/*printf("DEBUG: block %d : page %d : can write up to %d glyphs\n",
						n_block, n_current_page, n_write_glyph_num);*/ // debug
					n_write_glyph_num = min(n_write_glyph_num, n_remaining_glyphs);
					/*printf("DEBUG: block %d : page %d : will write %d glyphs\n",
						n_block, n_current_page, n_write_glyph_num);*/ // debug
					// calculate number of glyphs to store

					try {
						//n_glyph_info_num += n_write_glyph_num; // debug
						t_block_info.glyph_range_list.push_back(TBlockInfo::TGlyphRange(n_current_page,
							&r_page, n_current_glyph, n_current_glyph + n_write_glyph_num));
					} catch(std::bad_alloc &) {
						return false;
					}
					// add the range of glyphs to the meta block

					n_block_space -= sizeof(TPageInfo) + n_write_glyph_num * sizeof(TGlyphInfo);
					n_current_glyph += n_write_glyph_num;
					if(n_current_glyph == r_glyph_list.size()) {
						n_current_glyph = 0;
						++ n_current_page;
						++ p_page_it;
						if(p_page_it == p_end_it)
							break;
					}
					// handle page transitions
				}
			}
			// fill the block with data

			//printf("DEBUG: block %d : free space : %d B\n", n_block, n_block_space); // debug

			try {
				/*printf("DEBUG: block %d : %d x %d (capacity " PRIsizeB "B)\n", n_block,
					n_MetaBlock_Width(n_block), n_MetaBlock_Height(n_block),
					PRIsizeBparams(n_MetaBlock_Area(n_block)));
				printf("DEBUG: block %d : %d glyph infos (" PRIsizeB "B)\n", n_block,
					n_glyph_info_num, PRIsizeBparams(n_glyph_info_num * sizeof(TGlyphInfo) +
					t_block_info.glyph_range_list.size() * sizeof(TPageInfo)));*/ // debug
				m_block_info_list.push_back(t_block_info);
			} catch(std::bad_alloc &) {
				return false;
			}
			// add the block to the list (involves copying of std::vectors)
		}

		_ASSERTE(p_page_it == p_end_it && !n_current_glyph);
		// make sure all the glyphs fit into the info-blocks

		return p_page_it == p_end_it && !n_current_glyph;
	}

	/**
	 *	@brief writes a block with metadata to an image
	 *
	 *	@param[in,out] r_t_dest_bmp is allocated image with
	 *		at least the same resolution as the corresponding page
	 *	@param[in] n_block_id is zero-based index of metadata block
	 *		(must be less than n_MetaBlock_Num())
	 */
	void Write_MetaBlock(TBmp &r_t_dest_bmp, size_t n_block_id)
	{
		_ASSERTE(n_block_id < m_block_info_list.size());
		// make sure it's a valid id

		if(!n_block_id) {
			//m_n_char_written = 0; // debug

			_ASSERTE(!m_t_font_info.n_extension_block_num);
			m_t_font_info.n_extension_block_num = 0;
			// extension blocks are not supported by the writer at the moment

			CMetaBlockWriter writer(r_t_dest_bmp, n_block_id, m_block_info_list.size(),
				n_MetaBlock_Width(n_block_id), n_MetaBlock_Height(n_block_id), m_n_stream_id,
				m_t_font_info, m_p_s_font_face,
				m_block_info_list[n_block_id].glyph_range_list.size());
			// create the first writer (note it's initialized a bit
			// differently compared to the following ones)

			Write_MetaInfoBlock_Contents(writer, n_block_id);
			// write infoblock contents

			writer.Finalize();
			// calculate CRC32 for this particular block
		} else {
			CMetaBlockWriter writer(r_t_dest_bmp, n_block_id, m_block_info_list.size(),
				n_MetaBlock_Width(n_block_id), n_MetaBlock_Height(n_block_id), m_n_stream_id,
				m_block_info_list[n_block_id].glyph_range_list.size());
			// create the next writers

			Write_MetaInfoBlock_Contents(writer, n_block_id);
			// write infoblock contents

			writer.Finalize();
			// calculate CRC32 for this particular block
		}

		/*if(n_block_id == m_block_info_list.size() - 1)
			printf("DEBUG: written %d glyph infos in %d blocks\n", m_n_char_written, n_block_id + 1);*/ // debug
	}

protected:
	void Write_MetaInfoBlock_Contents(CMetaBlockWriter &writer, size_t n_block_id)
	{
		const TBlockInfo &r_t_block = m_block_info_list[n_block_id];

		/*size_t n_char_sum = 0;
		for(size_t i = 0, n = r_t_block.glyph_range_list.size(); i < n; ++ i) {
			const TBlockInfo::TGlyphRange &r_t_glyphs = r_t_block.glyph_range_list[i];
			n_char_sum += r_t_glyphs.n_last - r_t_glyphs.n_first;
			printf("DEBUG: meta info block %d : subblock %d : %d characters for page %d (0x%08x)\n",
				n_block_id, i, r_t_glyphs.n_last - r_t_glyphs.n_first, r_t_glyphs.n_page_index, r_t_glyphs.p_page);
		}
		printf("DEBUG: meta info block %d : %d characters in total\n", n_block_id, n_char_sum);*/ // debug

		for(size_t i = 0, n = r_t_block.glyph_range_list.size(); i < n; ++ i) {
			const TBlockInfo::TGlyphRange &r_t_glyphs = r_t_block.glyph_range_list[i];
			{
				TPageInfo t_info;
				t_info.n_page_id = r_t_glyphs.n_page_index;
				t_info.n_glyph_num = r_t_glyphs.n_last - r_t_glyphs.n_first;
				size_t n_result = writer.n_Write(&t_info, sizeof(TPageInfo));
				_ASSERTE(n_result == sizeof(TPageInfo));
			}
			// write TPageInfo

			{
				const std::vector<TGlyphInfo*> &r_glyph_list = r_t_glyphs.p_page->r_ItemList();
				// get the list of glyphs in the current page

				for(size_t i = r_t_glyphs.n_first; i < r_t_glyphs.n_last; ++ i) {
					size_t n_result = writer.n_Write((TGlyphInfo*)r_glyph_list[i],
						sizeof(TGlyphInfo));
					_ASSERTE(n_result == sizeof(TGlyphInfo));

					//++ m_n_char_written; // debug
				}
			}
			// write the TGlyphInfo for the specified range of glyphs
		}
	}

	inline size_t n_Block_HeaderSize(bool b_first_block)
	{
		if(b_first_block)
			return sizeof(TContainerInfo) + sizeof(TFontInfo) + strlen(m_p_s_font_face) * sizeof(char);
		else
			return sizeof(TContainerInfo);
	}

	inline size_t n_Blocks_HeaderSizes(size_t n_block_num)
	{
		_ASSERTE(n_block_num);

		return n_Block_HeaderSize(true) + n_Block_HeaderSize(false) * (n_block_num - 1);
	}

	inline size_t n_Blocks_PayloadSize(size_t n_block_num, size_t n_page_num)
	{
		size_t n_payload_size = n_page_num * sizeof(TPageInfo) +
			m_r_glyph_info_list.size() * sizeof(TGlyphInfo);
		size_t n_fragmentation_overhead = (n_block_num <= 1)? 0 :
			(n_block_num - 1) * (sizeof(TPageInfo) + sizeof(TGlyphInfo) - 1);
		return n_payload_size + n_fragmentation_overhead;
		// assumes glyph and page info fragmentation (ie. each block begins
		// with page info / glyph info which continues from the previous block,
		// except for the first one, of course)
	}

	inline size_t n_Max_Page_Num(size_t n_avg_block_area,
		size_t n_last_block_area, size_t n_block_num)
	{
		size_t n_blocks_capacity = n_last_block_area +
			n_avg_block_area * (n_block_num - 1);

		_ASSERTE(n_blocks_capacity >= n_Blocks_HeaderSizes(n_block_num));
		n_blocks_capacity -= n_Blocks_HeaderSizes(n_block_num);
		// subtract space taken up by the headers

		size_t n_raw_payload_size = m_r_glyph_info_list.size() * sizeof(TGlyphInfo);
		_ASSERTE(n_blocks_capacity >= n_raw_payload_size);
		n_blocks_capacity -= n_raw_payload_size;
		// subtract space taken up by the (raw) payload

		size_t n_fragmentation_overhead = (n_block_num <= 1)? 0 :
			(n_block_num - 1) * (sizeof(TPageInfo) + sizeof(TGlyphInfo) - 1);
		if(n_blocks_capacity < n_fragmentation_overhead)
			return 0; // none will fit (overhead is not accoounted for in some routines)
		n_blocks_capacity -= n_fragmentation_overhead;
		// subtract space taken up by the fragmentation (of both headers and data)

		return n_blocks_capacity / sizeof(TPageInfo);
		// calculate how much TPageInfo's fit in there, and subtract repeated
		// TPageInfo's at the block boundaries (worst-case)
	}

	void Make_Container(size_t n_required_area, size_t &r_n_width, size_t &r_n_height)
	{
		const size_t n_container_block_min_width = sizeof(uint32_t);
		// minimal width of a container block (must contain it's width in a single scanline)

		size_t n_best_width = max(n_container_block_min_width,
			size_t(sqrt(double(n_required_area))));
		size_t n_best_height = (n_required_area + n_best_width - 1) / n_best_width;
		_ASSERTE(n_required_area <= n_best_width * n_best_height);
		// do an initial guess

		size_t n_best_error = n_best_width * n_best_height - n_required_area;
		if(n_best_error > 0) {
			const size_t n_jitter = 50;
			for(size_t i = max(n_best_width, n_jitter + n_container_block_min_width) - n_jitter,
			   n = min(m_n_max_container_size, n_best_width + n_jitter); i < n; ++ i) {
				size_t n_width = i;
				size_t n_height = (n_required_area + n_width - 1) / n_width;
				_ASSERTE(n_required_area <= n_width * n_height);
				size_t n_error = n_width * n_height - n_required_area;
				if(n_best_error > n_error) {
					n_best_width = n_width;
					n_best_height = n_height;
				}
			}
		}
		// try to find a better solution

		if(n_best_width < n_best_height) {
			r_n_width = n_best_height;
			r_n_height = n_best_width;
		} else {
			r_n_width = n_best_width;
			r_n_height = n_best_height;
		}
		// this increases packing efficiency
	}

	void Do_MetaInfoBlocks_Layout()
	{
		size_t n_container_block_capacity = m_n_max_container_size *
			m_n_max_container_size - n_Block_HeaderSize(false);
		// capacity of a single container block

		size_t n_expected_block_num = max(size_t(1), (n_Blocks_PayloadSize(0, 0) +
			n_Block_HeaderSize(true)) / (n_container_block_capacity - n_Block_HeaderSize(false)));
		// try to estimate how many blocks are needed (excluding the TPageInfo's)

		size_t m_n_max_page_num;
		{
			float f_noblock_pages_glyphs_area = float(m_f_glyphs_area -
				n_expected_block_num * m_f_free_page_area * m_f_worst_case_efficiency);
			// area of glyphs without those, stored in pages with infoblocks
			
			float f_free_free_page_area = (float(m_n_page_size_padd) * m_n_page_size_padd);
			// area of free page without the infoblock

			m_n_max_page_num = n_expected_block_num + size_t(f_noblock_pages_glyphs_area /
				(f_free_free_page_area * m_f_worst_case_efficiency)) + m_n_page_num_overestimate;
			// ... and the rest is stored in the following pages (without infoblocks)
		}
		// estimate maximal number of pages (try to overestimate)
		// note this may be wrong in the end, and it may need to be recalculated

		size_t n_store_bytes = n_Blocks_HeaderSizes(n_expected_block_num) +
			n_Blocks_PayloadSize(n_expected_block_num, m_n_max_page_num);
		// nuber of bytes to store (font info block, all glyph infos, and all the leading page infos)

		//printf("DEBUG: n_store_bytes = %d\n", n_store_bytes); // debug

		/*printf("DEBUG: %d characters for %d pages in %d info blocks require " PRIsizeB "B\n",
			m_r_glyph_info_list.size(), m_n_max_page_num, n_expected_block_num,
			PRIsizeBparams(n_store_bytes));*/ // debug

		m_n_container_block_num = (n_store_bytes + n_container_block_capacity - 1) / n_container_block_capacity;
		// number of container blocks

		//printf("DEBUG: corrected block num: %d\n", m_n_container_block_num);

		const size_t n_container_block_min_width = sizeof(uint32_t);
		// minimal width of a container block (must contain it's width in a single scanline)

		m_n_avg_container_block_area = n_store_bytes / m_n_container_block_num;
		Make_Container(m_n_avg_container_block_area, m_n_avg_container_block_width,
			m_n_avg_container_block_height);
		m_n_avg_container_block_area = m_n_avg_container_block_width * m_n_avg_container_block_height;
		// calculate "average" container block area and dimensions

		while(m_n_container_block_num && n_store_bytes <
		   m_n_avg_container_block_area * (m_n_container_block_num - 1))
			-- m_n_container_block_num;
		// for large numbers of very small containers ...

		if(m_n_container_block_num > 1) {
			m_n_last_container_block_area = n_store_bytes -
				m_n_avg_container_block_area * (m_n_container_block_num - 1);
			Make_Container(m_n_last_container_block_area, m_n_last_container_block_width,
				m_n_last_container_block_height);
			m_n_last_container_block_area = m_n_last_container_block_width * m_n_last_container_block_height;
			// calculate last container block area and dimensions
		} else {
			m_n_last_container_block_area = m_n_avg_container_block_area;
			m_n_last_container_block_width = m_n_avg_container_block_width;
			m_n_last_container_block_height = m_n_avg_container_block_height;
			m_n_avg_container_block_area = 0;
			m_n_avg_container_block_width = 0;
			m_n_avg_container_block_height = 0;
			// if there's only a single container, then there's no average, only the last
		}

		m_n_max_store_page_num = n_Max_Page_Num(m_n_avg_container_block_area,
			m_n_last_container_block_area, m_n_container_block_num);

		//printf("DEBUG: m_n_max_store_page_num: %d\n", m_n_max_store_page_num); // debug
		/*printf("DEBUG: block size %d x %d\n",
			m_n_last_container_block_width, m_n_last_container_block_height);*/ // debug
	}
};

/*
 *								=== CBitmapFont ===
 */

CBitmapFont::CBitmapFont()
{
	memset(&m_t_font_info, 0, sizeof(TFontInfo));
	Defaults();
	// fill-in some defaults
}

CBitmapFont::~CBitmapFont()
{
	std::for_each(m_bitmap_list.begin(), m_bitmap_list.end(), DeleteBitmap);
}

const std::vector<TGlyphInfo> &CBitmapFont::r_Glyph_List() const
{
	return m_glyph_list;
}

const std::list<CBitmapFont::CPage> &CBitmapFont::r_Page_List() const
{
	return m_page_list;
}

// @note This list is normally empty, unless b_store_bitmaps is set in Create() or in Load().
const std::vector<TBmp*> &CBitmapFont::r_PageBitmap_List() const
{
	return m_bitmap_list;
}

// @todo - implement CGLBitmapFont2 (with texture array, custom geometry, and shader)

bool CBitmapFont::Load_Internal(CBitmapProducer &bitmap_producer,
	CBitmapCallback &bitmap_callback, bool b_store_bitmaps,
	bool b_read_font_info_only, uint32_t n_blank_color)
{
	m_page_list.clear();
	m_glyph_list.clear();
	std::for_each(m_bitmap_list.begin(), m_bitmap_list.end(), DeleteBitmap);
	m_bitmap_list.clear();
	// clear everything

	TContainerInfo t_first_container;
	CMetadataReader reader;
	for(size_t i = 0, n = 1; i < n; ++ i) {
		TBmp *p_bitmap;
		if(!(p_bitmap = bitmap_producer(i)))
			return false;
		// load the page

		if(!reader.Read_Metadata(*p_bitmap)) {
			p_bitmap->Delete();
			return false;
		}
		// read metadata from the page

		if(!i) {
			t_first_container = reader.t_Last_ContainerInfo();
			m_t_font_info = reader.t_FontInfo(); // before the first invokation of bitmap_callback
			if(!stl_ut::AssignCStr(m_s_font_face, reader.p_s_FontFace())) {
				p_bitmap->Delete();
				return false;
			}

			n = t_first_container.n_block_num;
			// make sure all the metablocks are decoded

			if(b_read_font_info_only) {
				p_bitmap->Delete();
				return true;
			}
			// in case the caller only wishes to decode font info, quit
		}
		// get font / container info from the first page

		if(i + 1 == n) {
			n = max(n, reader.r_Page_List().size());
			// make sure all the pages that are referenced are read
		}
		// on the last page with metablock ...

		if(i < t_first_container.n_block_num)
			reader.Blank(*p_bitmap, n_blank_color);
		// blank the metainfo block, if present

		if(!bitmap_callback(i, m_t_font_info.n_page_num/*n*/, *p_bitmap))
			return false;
		// call the bitmap consumer

		if(b_store_bitmaps) {
			if(!stl_ut::Resize_Add_1More(m_bitmap_list, p_bitmap)) {
				p_bitmap->Delete();
				return false;
			}
		} else
			p_bitmap->Delete();
	}
	// read the next pages

	if(!reader.b_Complete())
		return false;
	// check completeness before damaging the reader

	TGlyphInfo *p_address_check = &reader.r_Glyph_List()[0];
	reader.r_Glyph_List().swap(m_glyph_list);
	if(&m_glyph_list[0] != p_address_check) {
		fprintf(stderr, "error: swap() reallocated vector contents\n");
		return false;
	}
	reader.r_Page_List().swap(m_page_list);
	// get page / character data from the reader (damages it)

	return true;
}

bool CBitmapFont::Load(const char *p_s_filename, CBitmapCallback &bitmap_callback,
	bool b_store_bitmaps, uint32_t n_blank_color)
{
	CBitmapReader bitmap_reader(p_s_filename);
	return Load_Internal(bitmap_reader, bitmap_callback, b_store_bitmaps, false, n_blank_color);
}

bool CBitmapFont::Load(CBitmapProducer &bitmap_producer,
	CBitmapCallback &bitmap_callback, bool b_store_bitmaps, uint32_t n_blank_color)
{
	return Load_Internal(bitmap_producer, bitmap_callback, b_store_bitmaps, false, n_blank_color);
}

bool CBitmapFont::Read_FontInfo(const char *p_s_filename,
	TFontInfo &r_t_font_info, std::string &r_s_font_face)
{
	CBitmapReader bitmap_reader(p_s_filename);
	return Read_FontInfo(bitmap_reader, r_t_font_info, r_s_font_face); // don't repeat the same code twice
}

bool CBitmapFont::Read_FontInfo(CBitmapProducer &bitmap_producer,
	TFontInfo &r_t_font_info, std::string &r_s_font_face)
{
	CBitmapFont bf;
	CEmptyBitmapCallback bitmap_callback;
	if(!bf.Load_Internal(bitmap_producer, bitmap_callback, false, true, 0)) // don't care about the blanking color
		return false;
	r_t_font_info = bf.t_Font_Info(); // copy font info
	r_s_font_face.swap(bf.m_s_font_face); // exchange font face
	return true;
}

void CBitmapFont::Enable_MetaBlock_Allocation(bool _b_alloc_meta_blocks)
{
	b_alloc_meta_blocks = _b_alloc_meta_blocks;
}

void CBitmapFont::Enable_Metadata_Verify(bool _b_verify)
{
	b_verify = _b_verify;
}

void CBitmapFont::Enable_NPOT_Output(bool b_non_power_of_two_output)
{
	b_power_of_two_output = !b_non_power_of_two_output;
}

bool CBitmapFont::Request_UnicodeBlock(const char *p_s_block_name)
{
	size_t n_dummy = 0;
	std::vector<std::pair<int, int> > dummy;
	if(!CUnicodeBlocks::Codepoints_From_UnicodeNames(dummy, n_dummy,
	   1, &p_s_block_name, m_n_unicode_version_id))
		return false;
	return stl_ut::Resize_Add_1More(m_unicode_block_list, p_s_block_name);
}

bool CBitmapFont::Set_UnicodeVersion(const char *p_s_unicode_version)
{
	size_t n_unicode_version_id;
	if((n_unicode_version_id =
	   CUnicodeBlocks::n_Translate_UnicodeVersion(p_s_unicode_version)) == -1)
		return false;
	m_n_unicode_version_id = n_unicode_version_id;
	return true;
}

void CBitmapFont::Set_FontDecoration(bool b_italic, bool b_underline)
{
	m_t_font_info.b_italic = b_italic;
	m_t_font_info.b_underline = b_underline;
}

void CBitmapFont::Set_FontWeight(int n_font_weight)
{
	m_t_font_info.n_font_weight = n_font_weight;
}

void CBitmapFont::Set_Max_PageSize(size_t n_max_page_size)
{
	if(n_max_page_size < 64)
		return;
	_ASSERTE(n_max_page_size > 0);
	m_t_font_info.n_max_page_size = n_max_page_size;
}

void CBitmapFont::Set_PagePadding(size_t n_page_padding)
{
	if(n_page_padding >= 32)
		return;
	m_t_font_info.n_page_padding = n_page_padding;
}

void CBitmapFont::Set_GlyphTexturePadding(size_t n_glyph_padding)
{
	if(n_glyph_padding >= 32)
		return;
	m_t_font_info.n_glyph_tex_padding = n_glyph_padding;
}

void CBitmapFont::Set_GlyphGeometryPadding(size_t n_geom_padding)
{
	if(n_geom_padding >= 32)
		return;
	m_t_font_info.n_glyph_geom_padding = n_geom_padding;
}

void CBitmapFont::Defaults()
{
	Enable_MetaBlock_Allocation();
	Enable_Metadata_Verify();
	Enable_NPOT_Output();
	m_unicode_block_list.clear();
	m_n_unicode_version_id = 0;//Set_UnicodeVersion();
	Set_FontDecoration();
	Set_FontWeight();
	Set_Max_PageSize();
	Set_PagePadding();
	Set_GlyphTexturePadding();
	Set_GlyphGeometryPadding();
}

template <class _TySrc, class _TyDest = _TySrc>
class CAddressTransform {
protected:
	const _TySrc *m_p_src_list_base;
	_TyDest *m_p_dst_list_base;

public:
	CAddressTransform(const _TySrc *p_src_list_base, _TyDest *p_dst_list_base)
		:m_p_src_list_base(p_src_list_base), m_p_dst_list_base(p_dst_list_base)
	{}

	inline _TyDest *operator ()(const _TySrc *p_pointer) const
	{
		_ASSERTE(p_pointer >= m_p_src_list_base);
		return m_p_dst_list_base + (p_pointer - m_p_src_list_base);
	}
};

#if defined(_WIN32) || defined(_WIN64)

int CBitmapFont::n_Load_FontFile(const char *p_s_filename, std::vector<std::string> &r_s_font_faces)
{
	return bitmapfont2::CGlyphRenderer::CFontResourceLoader::n_Load_FontFile(p_s_filename, r_s_font_faces);
}

void CBitmapFont::Unload_FontFile(const char *p_s_filename)
{
	bitmapfont2::CGlyphRenderer::CFontResourceLoader::Unload_FontFile(p_s_filename);
}

#endif // _WIN32 || _WIN64

bool CBitmapFont::_Create(const char *p_s_font_face, int n_font_size,
	CBitmapCallback &bitmap_callback, bool b_store_bitmaps,
	CTexturePostprocessIface *p_postprocess, bool b_verbose)
{
	m_page_list.clear();
	m_glyph_list.clear();
	std::for_each(m_bitmap_list.begin(), m_bitmap_list.end(), DeleteBitmap);
	m_bitmap_list.clear();

	if(b_verbose)
		printf("building a list of codepoints ...\n");
	// verbose

	const char **p_uni_block_list;
	size_t n_uni_block_num;
	if(m_unicode_block_list.empty()) {
		static const char *p_default_uni_block_list[] = {"Basic Latin"};
		p_uni_block_list = p_default_uni_block_list;
		n_uni_block_num = sizeof(p_default_uni_block_list) /
			sizeof(p_default_uni_block_list[0]);
	} else {
		p_uni_block_list = &m_unicode_block_list[0];
		n_uni_block_num = m_unicode_block_list.size();
	}
	// get the list of required unicode blocks

	size_t n_glyph_num;
	std::vector<std::pair<int, int> > range_list;
	{
		range_list.clear();
		n_glyph_num = 0; // !!
		if(!CUnicodeBlocks::Codepoints_From_UnicodeNames(range_list, n_glyph_num,
		   n_uni_block_num, p_uni_block_list, m_n_unicode_version_id)) {
			if(b_verbose)
				fprintf(stderr, "error: failed to get list of codepoints (bad block name?)\n");
			return false;
		}
	}
	// build final range list

	int n_undisplayable_char = -1;//0x0180; // @todo - make this member, make it accessible to the user
	// undisplayable character checking (eliminate "squares" in the output by marking them)

	const size_t n_max_page_size = m_t_font_info.n_max_page_size;
	const size_t n_page_padding = m_t_font_info.n_page_padding;
	const size_t n_box_padding = m_t_font_info.n_glyph_tex_padding + m_t_font_info.n_glyph_geom_padding; // glyph padding is both texture and geometry
	// page and box padding

	const float f_slack_space_resize_thresh = .1f; // @todo - make this member, make it accessible to the user
	// amount of unused space in order to try to resize a page

	const float f_rotation_thresh = .5f; // @todo - make this member, make it accessible to the user
	// rotation threshold (improves packing efficiency)

	if(n_page_padding >= 32 || n_max_page_size < 64) {
		if(b_verbose)
			fprintf(stderr, "error: bad page padding / page size\n");
		return false;
	}
	// check params

	if(b_verbose)
		printf("initializing glyph renderer ...\n");
	// verbose

	const bool b_use_cleartype = false;
	CGlyphRenderer gr(p_s_font_face, n_font_size, m_t_font_info.n_font_weight,
		(m_t_font_info.b_italic)? true : false, (m_t_font_info.b_underline)? true : false, b_use_cleartype);
	if(!gr.b_Status()) {
		if(b_verbose)
			fprintf(stderr, "error: failed to initialize glyph renderer\n");
		return false;
	}
	// create font renderer

	gr.Get_FontMetrics(m_t_font_info);
	// get font parameters

	m_t_font_info.n_font_size = n_font_size;
	m_t_font_info.n_extension_block_num = 0; // !!
	m_t_font_info.n_font_face_length = strlen(p_s_font_face);
	if(!stl_ut::AssignCStr(m_s_font_face, p_s_font_face)) { // before bitmap_callback!
		if(b_verbose)
			fprintf(stderr, "error: not enough memory\n");
		return false;
	}
	// fill the font info structure

	if(b_verbose)
		printf("getting glyph metrics ...\n");
	// verbose

	size_t n_discarded_num = 0; // !!
	std::vector<TGlyphInfo> glyph_info_list;
	if(!Get_GlyphInfoList(glyph_info_list, n_discarded_num, range_list, gr)) {
		if(b_verbose)
			fprintf(stderr, "error: not enough memory\n");
		return false;
	}
	// get glyph infos

	int n_page_resize = n_box_padding - 2 * n_page_padding;
	size_t n_page_size_padd = n_max_page_size + n_page_resize;
	// calculate a new page size

	size_t n_max_container_size = n_max_page_size / 2;
	// get maximal container size

	if(b_verbose)
		printf("preparing metadata layout ...\n");
	// verbose

	CMetadataWriter meta_layout(p_s_font_face, m_t_font_info, n_page_size_padd,
		n_max_container_size, glyph_info_list);
	// prepare metadata block layout

	if(b_verbose)
		printf("building glyph layout ...\n");
	// verbose

	CMetadataReader meta_reader;
	// for verification purposes

	{
		std::list<CBitmapFontPage> page_list;
		if(!Build_GlyphLayout(page_list, meta_layout, b_alloc_meta_blocks,
		   glyph_info_list, n_max_page_size, n_box_padding, n_page_padding,
		   b_power_of_two_output, b_verbose, f_rotation_thresh, f_slack_space_resize_thresh)) {
			if(b_verbose)
				fprintf(stderr, "error: Build_GlyphLayout() failed\n");
			return false;
		}
		// create the final page layout

		{
			m_t_font_info.n_max_page_width = 0;
			m_t_font_info.n_max_page_height = 0;
			std::list<CBitmapFontPage>::const_iterator p_page_it = page_list.begin();
			for(size_t i = 0, n = page_list.size(); i < n; ++ i, ++ p_page_it) {
				const CBitmapFontPage &r_page = *p_page_it;
				const std::vector<TGlyphInfo*> &r_glyph_list = r_page.r_ItemList();
				// get the page and the list of items in it

				uint32_t n_packed_width = r_page.n_Width();
				uint32_t n_packed_height = r_page.n_Height();
				// get the dimension of the output

				if(m_t_font_info.n_max_page_width < n_packed_width)
					m_t_font_info.n_max_page_width = n_packed_width;
				if(m_t_font_info.n_max_page_height < n_packed_height)
					m_t_font_info.n_max_page_height = n_packed_height;
				// find maxima
			}
			if(b_power_of_two_output) {
				m_t_font_info.n_max_page_width = n_Make_POT(m_t_font_info.n_max_page_width);
				m_t_font_info.n_max_page_height = n_Make_POT(m_t_font_info.n_max_page_height);
			}
		}
		// fill-in maximal page dimensions (the point of the last change
		// to m_t_font_info; bitmap_callback should not be called before)

		_ASSERTE(page_list.size() < n_MaxIntValue(m_t_font_info.n_page_num));
		m_t_font_info.n_page_num = page_list.size();
		// fill-in number of pages (handy for texture allocation, etc.)

		meta_layout.Update_FontInfo(m_t_font_info);
		// ...

		if(b_verbose)
			printf("compiling metadata layout ...\n");
		// verbose

		if(b_alloc_meta_blocks && !meta_layout.Prepare_PageMeta_Layout(page_list)) {
			if(b_verbose)
				fprintf(stderr, "error: Prepare_PageMeta_Layout() failed\n");
			return false;
		}
		// prepare metadata layout (now that the number and sizes of the pages are known)

		if(b_verbose)
			printf("rendering ...\n");
		// verbose

		std::list<CBitmapFontPage>::const_iterator p_page_it = page_list.begin();
		for(size_t i = 0, n = page_list.size(); i < n; ++ i, ++ p_page_it) {
			const CBitmapFontPage &r_page = *p_page_it;
			const std::vector<TGlyphInfo*> &r_glyph_list = r_page.r_ItemList();
			// get the page and the list of items in it

			uint32_t n_packed_width = r_page.n_Width();
			uint32_t n_packed_height = r_page.n_Height();
			// get the dimension of the output

			//printf("bitmap %dx%d (block %d/%d %dx%d)\n", n_packed_width, n_packed_height,
			//	i, n_container_block_num, n_container_block_width, n_container_block_height);
			// debug

			TBmp *p_bitmap;
			if(!(p_bitmap = TBmp::p_Alloc(n_packed_width, n_packed_height, true, false))) {
				if(b_verbose)
					fprintf(stderr, "error: not enough memory\n");
				return false;
			}
			p_bitmap->Clear(0);
#ifdef __DEBUG_COLORS
			p_bitmap->b_grayscale = false; // so we can see the colors
			p_bitmap->Clear(0xff00ff00U); // debug green
#endif // __DEBUG_COLORS
			// alloc and clear page bitmap

			if(!p_postprocess && b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())
				meta_layout.Write_MetaBlock(*p_bitmap, i);
			// write the container blocks now if there is no postprocessing
			// (to make sure it does not collide with the characters)

			//printf("DEBUG: page %d : %d characters\n", i, (*p_page_it).r_ItemList().size()); // debug

			for(size_t j = 0, m = r_glyph_list.size(); j < m; ++ j) {
				TGlyphInfo t_glyph = *r_glyph_list[j];
				// get glyph info

				TGlyphInfo t_tmp;
				CGlyphRenderer::TRectangle t_raster_info;
				if(!gr.RenderGlyph(t_glyph.n_code, t_tmp, t_raster_info)) {
					p_bitmap->Delete();
					if(b_verbose)
						fprintf(stderr, "error: RenderGlyph() failed\n");
					return false;
				}
				_ASSERTE(t_tmp.n_bitmap_width == t_glyph.n_bitmap_width);
				_ASSERTE(t_tmp.n_bitmap_height == t_glyph.n_bitmap_height);
				// render the glyph to offscreen bitmap

				gr.Copy_Raster(p_bitmap->p_buffer + (t_glyph.n_bitmap_pos_x +
					t_glyph.n_bitmap_pos_y * p_bitmap->n_width),
					p_bitmap->n_width, (t_glyph.b_rotation)? 1 : 0, t_raster_info);
				// copy the rendered glyph to the bitmap
			}
			// copy glyphs to the bitmap

			if(p_postprocess) {
				int n_meta_block_width = 0, n_meta_block_height = 0;
				if(b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num()) {
					n_meta_block_width = meta_layout.n_MetaBlock_Width(i);
					n_meta_block_width = meta_layout.n_MetaBlock_Height(i);
				}
				p_postprocess->Postprocess(*p_bitmap, n_meta_block_width, n_meta_block_height,
					min(m_t_font_info.n_glyph_geom_padding, m_t_font_info.n_glyph_tex_padding));
			}
			// apply postprocessing, if any

			if(p_postprocess && b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())
				meta_layout.Write_MetaBlock(*p_bitmap, i);
			// write the container blocks after postprocessing

			if(b_verify && b_alloc_meta_blocks && !meta_reader.Read_Metadata(*p_bitmap)) {
				if(b_verbose)
					fprintf(stderr, "error: metadata reader failed\n");
				p_bitmap->Delete();
				return false;
			}
			// test metadata readback

			if(!bitmap_callback(i, n, *p_bitmap)) {
				p_bitmap->Delete();
				return false;
			}
			// pass the bitmap to the consumer

			if(b_store_bitmaps) {
				if(!stl_ut::Resize_Add_1More(m_bitmap_list, p_bitmap)) {
					if(b_verbose)
						fprintf(stderr, "error: not enough memory\n");
					p_bitmap->Delete();
					return false;
				}
			} else
				p_bitmap->Delete();
			// cleanup
		}
		// rasterize pages and save them to a file

		try {
			if(!(b_verify && b_alloc_meta_blocks)) {
				m_glyph_list.swap(glyph_info_list);
				// just swap

				std::list<CBitmapFontPage>::const_iterator p_page_it = page_list.begin(), p_end_it = page_list.end();
				for(; p_page_it != p_end_it; ++ p_page_it) {
					const CBitmapFontPage &r_page = *p_page_it;

					m_page_list.push_back(CPage(r_page.n_Width(), r_page.n_Height()));

					const std::vector<TGlyphInfo*> &r_item_list_src = r_page.r_ItemList();
					std::vector<TGlyphInfo*> &r_item_list_dst = m_page_list.back().r_ItemList();

					r_item_list_dst.insert(r_item_list_dst.begin(), r_item_list_src.begin(), r_item_list_src.end());
				}
				// copy pages and their item lists (the address of glyph infos didn't change)
			} else {
				m_glyph_list.resize(glyph_info_list.size());
				std::copy(glyph_info_list.begin(), glyph_info_list.end(), m_glyph_list.begin());
				// copy the glyph list (can't swap because of verify)

				const TGlyphInfo *p_src_list_base = &glyph_info_list[0];
				TGlyphInfo *p_dst_list_base = (TGlyphInfo*)&m_glyph_list[0];
				// need to transform pointer addresses from one list to the other

				std::list<CBitmapFontPage>::const_iterator p_page_it = page_list.begin(), p_end_it = page_list.end();
				for(; p_page_it != p_end_it; ++ p_page_it) {
					const CBitmapFontPage &r_page = *p_page_it;

					m_page_list.push_back(CPage(r_page.n_Width(), r_page.n_Height()));

					const std::vector<TGlyphInfo*> &r_item_list_src = r_page.r_ItemList();

					std::vector<TGlyphInfo*> &r_item_list_dst = m_page_list.back().r_ItemList();

					r_item_list_dst.resize(r_item_list_src.size());
					std::transform(r_item_list_src.begin(), r_item_list_src.end(), r_item_list_dst.begin(),
						CAddressTransform<TGlyphInfo>(p_src_list_base, p_dst_list_base));
				}
				// copy pages, transform addresses of glyph infos
			}
		} catch(std::bad_alloc&) {
			if(b_verbose)
				fprintf(stderr, "error: not enough memory\n");
			return false;
		}
		// copy the page list
	}

	if(b_verbose) {
		printf("done. produced %d glyphs (excluding %d discarded), %d page%s\n",
			n_glyph_num - n_discarded_num, n_discarded_num, m_page_list.size(),
			(m_page_list.size() > 1)? "s" : "");
	}
	// verbose

	if(b_verify && b_alloc_meta_blocks && meta_reader.b_Complete()) {
		bool b_difference = false;
		do {
			const std::list<CMetadataReader::CPage> &r_page_list = meta_reader.r_Page_List();
			if(r_page_list.size() != m_page_list.size()) {
				//fprintf(stderr, "error: page count mismatch\n"); // debug
				b_difference = true;
				break;
			}
			// check page count

			std::list<CPage>::const_iterator p_page_it = m_page_list.begin();
			std::list<CMetadataReader::CPage>::const_iterator p_read_page_it = r_page_list.begin();
			for(size_t i = 0, n = m_page_list.size(); i < n; ++ i, ++ p_page_it, ++ p_read_page_it) {
				const CPage &r_page = *p_page_it;
				const CMetadataReader::CPage &r_read_page = *p_read_page_it;
				if(r_page.n_Width() != r_read_page.n_Width() ||
				   r_page.n_Height() != r_read_page.n_Height()) {
					//fprintf(stderr, "error: page resolution mismatch\n"); // debug
					b_difference = true;
					break;
				}
				if(r_page.r_ItemList().size() != r_read_page.r_ItemList().size()) {
					/*fprintf(stderr, "error: page glyph count mismatch (page %d: %d orig / %d read)\n",
						i, r_page.r_ItemList().size(), r_read_page.r_ItemList().size());*/ // debug
					b_difference = true;
					break;
				}
				if(!b_difference) {
					const std::vector<TGlyphInfo*> &r_page_list = r_page.r_ItemList();
					const std::vector<TGlyphInfo*> &r_read_page_list = r_read_page.r_ItemList();
					for(size_t j = 0, m = r_page_list.size(); j < m; ++ j) {
						TGlyphInfo t_glyph = *r_page_list[j];
						TGlyphInfo t_glyph2 = *r_read_page_list[j];
						if(t_glyph.n_code != t_glyph2.n_code) {
							//fprintf(stderr, "error: character code mismatch in page %d\n", i); // debug
							b_difference = true;
							break;
						}
						if(memcmp(&t_glyph2, &t_glyph, sizeof(TGlyphInfo))) {
							//fprintf(stderr, "error: glyph positioning mismatch in page %d\n", i); // debug
							b_difference = true;
							break;
						}
					}
				}
			}
			if(b_difference)
				break;
			// check page contents

			const std::vector<TGlyphInfo> &r_glyph_list = meta_reader.r_Glyph_List();
			if(r_glyph_list.size() != glyph_info_list.size()) {
				//fprintf(stderr, "error: character count mismatch\n"); // debug
				b_difference = true;
				break;
			}
			// check character count

			for(size_t i = 0, n = glyph_info_list.size(); i < n; ++ i) {
				TGlyphInfo t_glyph = glyph_info_list[i];
				b_difference = true; // assume not found
				for(size_t j = 0; j < n; ++ j) {
					if(r_glyph_list[j].n_code == t_glyph.n_code) {
						if(memcmp(&r_glyph_list[j], &t_glyph, sizeof(TGlyphInfo))) {
							//fprintf(stderr, "error: glyph positioning mismatch\n"); // debug
							break;
						}
						b_difference = false; // clear the difference
						break;
					}
				}
				if(b_difference) {
					//fprintf(stderr, "error: character code mismatch\n"); // debug
					break;
				}
			}
			// check character positions
		} while(0);
		// check whether the decoded datastream equals generated values

		if(b_difference) {
			//fprintf(stderr, "error: metadata reader complete but different\n"); // debug
			return false;
		}
	} else if(b_alloc_meta_blocks && b_verify) {
		//fprintf(stderr, "error: metadata reader indicates incomplete stream\n"); // debug
		return false;
	}
	// test metadata readback

	return true;
}

inline void CBitmapFont::DeleteBitmap(TBmp *p_bitmap)
{
	p_bitmap->Delete();
}

bool CBitmapFont::Get_GlyphImage(TBmp &r_t_bitmap, CGlyphRenderer &r_gr,
	int n_angle, CGlyphRenderer::TRectangle t_raster_info)
{
	TBmp t_bitmap;
	t_bitmap.b_grayscale = true;
	t_bitmap.b_alpha = false;
	t_bitmap.n_former_bpc = 8;
	t_bitmap.n_width = (n_angle & 1)? t_raster_info.n_height : t_raster_info.n_width;
	t_bitmap.n_height = (n_angle & 1)? t_raster_info.n_width : t_raster_info.n_height;
	if(!(t_bitmap.p_buffer = new(std::nothrow) uint32_t[t_raster_info.n_width * t_raster_info.n_height]))
		return false;
	// create bitmap

	r_gr.Copy_Raster(t_bitmap.p_buffer, t_bitmap.n_width, n_angle, t_raster_info);
	// copy raster

	r_t_bitmap = t_bitmap;

	return true;
}

bool CBitmapFont::Get_GlyphInfoList(std::vector<TGlyphInfo> &glyph_info_list,
	size_t &n_discarded_num, const std::vector<std::pair<int, int> > &range_list,
	CGlyphRenderer &gr, int n_undisplayable_char)
{
	/*glyph_info_list.clear();
	n_discarded_num = 0;*/
	// don't do this

	TBmp t_uchar_bmp = {0};
	if(n_undisplayable_char != -1) {
		TGlyphInfo t_char_info;
		CGlyphRenderer::TRectangle t_raster_info;
		if(!gr.RenderGlyph(n_undisplayable_char, t_char_info, t_raster_info))
			return false;
		if(!Get_GlyphImage(t_uchar_bmp, gr, 0, t_raster_info))
			return false;
	}
	// load image of an undisplayable glyph (a square under windows)

	for(size_t j = 0, m = range_list.size(); j < m; ++ j) {
		for(int i = range_list[j].first; i <= range_list[j].second; ++ i) {
			if(i == n_undisplayable_char) {
				++ n_discarded_num;
				continue;
			}
			// early detect undisplayable characters

			TGlyphInfo t_glyph_info;
			CGlyphRenderer::TRectangle t_raster_info;
			if(!gr.RenderGlyph(i, t_glyph_info, t_raster_info)) {
				if(t_uchar_bmp.p_buffer)
					delete[] t_uchar_bmp.p_buffer;
				return false;
			}
			// render a glyph to get it's raster dimensions

			if(t_raster_info.n_width <= 1 && t_raster_info.n_height <= 1) { // characters, such as space, etc.
				++ n_discarded_num;
				continue;
			}
			if(n_undisplayable_char != -1) {
				TBmp t_char_bmp;
				if(!Get_GlyphImage(t_char_bmp, gr, 0, t_raster_info)) {
					if(t_uchar_bmp.p_buffer)
						delete[] t_uchar_bmp.p_buffer;
					return false;
				}
				bool b_undisplayable = t_char_bmp.n_width == t_uchar_bmp.n_width &&
					t_char_bmp.n_height == t_uchar_bmp.n_height &&
					!memcmp(t_char_bmp.p_buffer, t_uchar_bmp.p_buffer,
					t_char_bmp.n_width * t_char_bmp.n_height * sizeof(uint32_t));
				delete[] t_char_bmp.p_buffer;
				if(b_undisplayable) {
					++ n_discarded_num;
					continue;
				}
			}
			// detect undisplayable characters

			try {
				glyph_info_list.push_back(t_glyph_info);
			} catch(std::bad_alloc&) {
				if(t_uchar_bmp.p_buffer)
					delete[] t_uchar_bmp.p_buffer;
				return false;
			}
			// add glyph information to the list
		}
	}
	// iterate through glyphs, discard undisplayable ones, collect their sizes

	if(t_uchar_bmp.p_buffer)
		delete[] t_uchar_bmp.p_buffer;
	// don't need this anymore

	return true;
}

inline TGlyphInfo CBitmapFont::t_Deref_BoxAdapter(const TGlyphInfo *ptr)
{
	return *ptr;
}

bool CBitmapFont::Build_GlyphLayout(std::list<CBitmapFontPage> &page_list,
	CMetadataWriter &meta_layout, bool b_alloc_meta_blocks, std::vector<TGlyphInfo> &glyph_info_list,
	size_t n_max_page_size, size_t n_box_padding, size_t n_page_padding, bool b_POT_output, bool b_verbose,
	float f_rotation_thresh, float f_slack_space_resize_thresh)
{
	page_list.clear();

	// to achieve that the boxes will have certain minimal distance from each other,
	// it is necessary to increase box size accordingly, and to increase area width and height

	// to achieve that the boxes will have certain minimal distance from the sides (required
	// for geom padding), it is necessary to decrease area width and height (not really needed
	// since the texture coordinate clipping will do the job at the borders (provided there is
	// at least a single pixel of the border))

	// note that the data area will be replaced by solid black in rendering mode; it is therefore
	// not required to maintain any padding in there

	int n_page_resize = n_box_padding - 2 * n_page_padding;
	int n_box_offset = n_page_padding;
	int n_box_resize = n_box_padding;
	int n_contents_resize = -n_box_resize + 2 * n_box_offset; // todo - is this right? (used to be 1 * n_box_offset)
	// transformation to page and box size to achieve such transformation

	size_t n_page_size_padd = n_max_page_size + n_page_resize;
	// calculate a new page size

	size_t n_max_container_size = n_max_page_size / 2;
	// get maximal container size

	for(size_t i = 0, n = glyph_info_list.size(); i < n; ++ i) {
		TGlyphInfo &r_t_glyph = glyph_info_list[i];
		r_t_glyph.n_bitmap_width += n_box_padding;
		r_t_glyph.n_bitmap_height += n_box_padding;
	}
	// forward padding transform

	for(;;) {
		if(b_alloc_meta_blocks) {
			for(size_t i = 0, n = meta_layout.n_MetaBlock_Num(); i < n; ++ i) {
				try {
					page_list.push_back(CBitmapFontPage(n_page_size_padd, n_page_size_padd));
				} catch(std::bad_alloc&) {
					return false;
				}
				// add a new page (a large one)

				TGlyphInfo t_container_block;
				t_container_block.b_rotation = false;
				t_container_block.n_bitmap_pos_x = 0;
				t_container_block.n_bitmap_pos_y = 0;
				t_container_block.n_bitmap_width = meta_layout.n_MetaBlock_Width(i);
				t_container_block.n_bitmap_height = meta_layout.n_MetaBlock_Height(i);
				// position the container block

				if(!page_list.back().Set_OffArea(t_container_block))
					return false;
				// set off-limits area for the container block
			}
		}
		// pre-create pages that need to contain container blocks

		CBitmapFontBPSolver::Prepare_Items(glyph_info_list, true, true, false);
		// prepare glyphs to be inserted to the pages

		if(!CBitmapFontBPSolver::Best_Fit(page_list,
		   glyph_info_list, CBitmapFontBPSolver::CBasicPageFactory(
		   n_page_size_padd, n_page_size_padd), true, f_rotation_thresh))
			return false;
		// pack items to pages, create as many pages as needed

		if(b_alloc_meta_blocks && page_list.size() > meta_layout.n_MaxStorage_Page_Num()) {
			if(b_verbose) {
				fprintf(stderr, "warning: number of pages was undersetimated"
					" (there are %d pages, %d was expected)\n",
					page_list.size(), meta_layout.n_MaxStorage_Page_Num());
			}
			meta_layout.Increase_PageEstimate(page_list.size() - meta_layout.n_MaxStorage_Page_Num());
			page_list.clear(); // !!
			continue;
		}
		// handle larger number of pages than expected (metalayout manager
		// needs to reallocate meta blocks then)

		{
			std::list<CBitmapFontPage>::iterator p_page_it = page_list.begin();
			for(size_t i = 0, n = page_list.size(); i < n; ++ i, ++ p_page_it) {
				CBitmapFontPage &r_page = *p_page_it;
				const std::vector<TGlyphInfo*> &r_glyph_list = r_page.r_ItemList();
				// get the page and the list of items in it

				uint32_t n_container_block_width = (b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())?
					meta_layout.n_MetaBlock_Width(i) : 0;
				uint32_t n_container_block_height = (b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())?
					meta_layout.n_MetaBlock_Height(i) : 0;
				// get the meta block size

				int n_contents_width = max(0, int(r_page.n_BoundingBox_Width() + n_contents_resize));
				int n_contents_height = max(0, int(r_page.n_BoundingBox_Height() + n_contents_resize));
				// calculate dimensions of contents

				uint32_t n_packed_width = max(n_container_block_width, uint32_t(n_contents_width /*+ 1*/));
				uint32_t n_packed_height = max(n_container_block_height, uint32_t(n_contents_height /*+ 1*/));
				// calculate minimal dimension of the output

				if(b_POT_output) {
					n_packed_width = n_Make_POT(n_packed_width);
					n_packed_height = n_Make_POT(n_packed_height);
				}
				// calculate power-of-two dimension of the output

				float f_slack_space_ratio = (float(n_packed_width * n_packed_height) -
					r_page.n_BoundingBox_Width() * r_page.n_BoundingBox_Height()) /
					(n_packed_width * n_packed_height);
				float f_side_ratio = float(min(n_contents_width, n_contents_height)) /
					max(n_contents_width, n_contents_height);
				const float f_side_ratio_thresh = .25f; // if one of the sides is four times smaller than the other, it's time to reshape
				if((n_packed_width == n_max_page_size && n_packed_height == n_max_page_size) ||
				   (f_slack_space_ratio < f_slack_space_resize_thresh && f_side_ratio > f_side_ratio_thresh))
					continue;
				// skip tightly packed pages

				std::vector<TGlyphInfo> glyph_list_copy;
				try {
					glyph_list_copy.resize(r_glyph_list.size());
					std::transform(r_glyph_list.begin(), r_glyph_list.end(),
						glyph_list_copy.begin(), t_Deref_BoxAdapter);
				} catch(std::bad_alloc&) {
					return false;
				}
				// make a copy of the glyph info list so the generated
				// glyph positions can be reverted in case
				// it's not possible to make the page any smaller

				//CBinPackingSolver<uint32_t, TGlyphInfo>::Prepare_Items(glyph_list_copy, false, true, false);
				// prepare glyphs to be inserted to the pages (do *not* sort!)

				bool b_found = false;
				for(int n_division = 2 * n_Log2(n_max_page_size); n_division > 0; -- n_division) {
					size_t n_new_width = n_max_page_size >> (n_division / 2);
					size_t n_new_height = n_max_page_size >> ((n_division + 1) / 2);
					size_t n_new_width_padd = n_new_width + n_page_resize;
					size_t n_new_height_padd = n_new_height + n_page_resize;
					// create a new width / height

					if(n_container_block_width >= n_new_width_padd ||
					   n_container_block_height >= n_new_height_padd)
						continue;
					// the metadata block wouldn't fit

					try {
						page_list.push_back(CBitmapFontPage(n_new_width_padd, n_new_height_padd));
					} catch(std::bad_alloc&) {
						return false;
					}
					std::list<CBitmapFontPage>::iterator p_new_page_it = -- page_list.end();
					CBitmapFontPage &r_new_page = *p_new_page_it; // insertion moves the iterator to the right
					// create a new page

					if(b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num()) {
						TGlyphInfo t_container_block;
						t_container_block.b_rotation = false;
						t_container_block.n_bitmap_pos_x = 0;
						t_container_block.n_bitmap_pos_y = 0;
						t_container_block.n_bitmap_width = n_container_block_width;
						t_container_block.n_bitmap_height = n_container_block_height;
						// position the container block

						_ASSERTE(n_container_block_width < n_new_width_padd);
						_ASSERTE(n_container_block_height < n_new_height_padd);
						// makes sure it fits (checked above)

						if(!r_new_page.Set_OffArea(t_container_block))
							return false;
						// set off-limits area for the container block
					}
					// put there a container block, if needed

					bool b_added = true; // in extreme case of glyph_list_copy.empty()
					for(size_t j = 0, m = glyph_list_copy.size(); j < m; ++ j) {
						if(!r_new_page.Add_Item(b_added, *r_glyph_list[j])) {
							return false;
						}
						if(!b_added) {
							if(j > f_rotation_thresh * m) {
								CBoxAdapter::Turn(*r_glyph_list[j]);
								if(!r_new_page.Add_Item(b_added, *r_glyph_list[j]))
									return false;
								if(!b_added)
									break;
							} else
								break;
						}
					}
					// attempts to add all the glyphs to the smaller page

					if(b_added) {
						n_packed_width = n_Make_POT(max(n_container_block_width,
							uint32_t(max(0, int(r_new_page.n_BoundingBox_Width() - n_box_resize + n_box_offset)))));
						n_packed_height = n_Make_POT(max(n_container_block_height,
							uint32_t(max(0, int(r_new_page.n_BoundingBox_Height() - n_box_resize + n_box_offset)))));
						//_ASSERTE(n_packed_width == n_new_width && n_packed_height <= n_new_height); // not always true, width can be smaller too (depends on the packing algorithm)
						// @todo - is this supposed to be always POT?
						// calculate a new bitmap width

						page_list.splice(p_page_it, page_list, p_new_page_it);
						// move the new page from the end of the list to the correct position

						std::list<CBitmapFontPage>::iterator p_old_page_it = p_page_it;
						// remember which page to erase

						-- p_page_it;
						// move the iterator to look at the newly inserted page

						page_list.erase(p_old_page_it);
						// erase the old page

						b_found = true;
						break;
					} else {
						page_list.erase(p_new_page_it);
						// erase the new page otherwise
					}
				}
				// try different sizes of the page, from the smallest one

				if(!b_found) {
					if(b_verbose)
						fprintf(stderr, "warning: page %d failed to downsize\n", i); // debug

					for(size_t j = 0, m = glyph_list_copy.size(); j < m; ++ j)
						*r_glyph_list[j] = glyph_list_copy[j];
					// revert glyph positions to the originals, delete the new page
					// (no way to do this using std::transform / std::copy)
				}
			}
		}
		// handle pages with too much unused space (repack into smaller page; address of data doesn't change)

		break;
		// once all metainfo blocks fit in the pages, quit
	}
	// create an optimized glyph layout

	for(size_t i = 0, n = glyph_info_list.size(); i < n; ++ i) {
		TGlyphInfo &r_t_glyph = glyph_info_list[i];
		r_t_glyph.n_bitmap_width -= n_box_resize;
		r_t_glyph.n_bitmap_height -= n_box_resize;
		r_t_glyph.n_bitmap_pos_x += n_box_offset;
		r_t_glyph.n_bitmap_pos_y += n_box_offset;
	}
	// backward padding transform, offset to the real position

	std::list<CBitmapFontPage>::iterator p_page_it = page_list.begin(), p_end_it = page_list.end();
	for(size_t i = 0; p_page_it != p_end_it; ++ p_page_it, ++ i) {
		CBitmapFontPage &r_page = *p_page_it;
		// get the page

		uint32_t n_container_block_width = (b_alloc_meta_blocks &&
			i < meta_layout.n_MetaBlock_Num())? meta_layout.n_MetaBlock_Width(i) : 0;
		uint32_t n_container_block_height = (b_alloc_meta_blocks &&
			i < meta_layout.n_MetaBlock_Num())? meta_layout.n_MetaBlock_Height(i) : 0;
		// get the meta block size

		int n_contents_width = max(0, int(r_page.n_BoundingBox_Width() + n_contents_resize));
		int n_contents_height = max(0, int(r_page.n_BoundingBox_Height() + n_contents_resize));
		// calculate dimensions of contents

		uint32_t n_packed_width = max(n_container_block_width, uint32_t(n_contents_width /*+ 1*/));
		uint32_t n_packed_height = max(n_container_block_height, uint32_t(n_contents_height /*+ 1*/));
		// calculate minimal dimension of the output

		if(b_POT_output) {
			n_packed_width = n_Make_POT(n_packed_width);
			n_packed_height = n_Make_POT(n_packed_height);
		}
		// calculate power-of-two dimension of the output

		r_page.Set_Size(n_packed_width, n_packed_height);
		// set the final size of the page
	}
	// calculate the final size of the pages

	return true;
}

/*
 *								=== ~CBitmapFont ===
 */
