/*
								+--------------------------------+
								|                                |
								|   ***  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) {
			CFontResourceLoader::Unload_FontFile(m_p_s_filename); // don't leave it loaded
			free((void*)m_p_s_filename); // allocated by strdup()
		}
	}

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

	bool b_SupportsKerning() const
	{
		HDC h_dc = m_p_bitmap->h_GetDC();
		HGDIOBJ h_prev_font = SelectObject(h_dc, m_h_font);
		bool b_result = (GetFontLanguageInfo(h_dc) & GCP_USEKERNING) == GCP_USEKERNING;
		SelectObject(h_dc, h_prev_font);
		m_p_bitmap->ReleaseDC();
		return b_result;
	}

	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 (f_ixme - do windows support that?) // no, it seems it does not (windows XP x64 does not but windows 7 seems to be fine)
		}*/
		_ASSERTE(sizeof(wchar_t) == sizeof(uint16_t));
		int n_strlen = CUniConv::n_EncodeCharacter_UTF16_LE(p_s_text,
			2 * sizeof(wchar_t), n_utf32) / sizeof(wchar_t);
		_ASSERTE(n_strlen != 0 && n_strlen <= 2); // 1 or 2 code points
		p_s_text[n_strlen] = 0; // terminate
		// 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, n_strlen/*int(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, n_strlen/*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, n_strlen/*(unsigned int)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 = int(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 = int(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 = int(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 = int(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
	}

	bool b_SupportsKerning() const
	{
		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(t_pg_info.n_glyph_num && (!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 <= INT_MAX && n_container_height <= INT_MAX);
			_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 = int(n_container_width);
			m_t_container_info.n_container_height = int(n_container_height);
			m_t_container_info.n_crc32 = CCrc_32::n_Start();
			m_t_container_info.n_stream_id = n_stream_id;
			_ASSERTE(n_block_id <= UINT32_MAX);
			m_t_container_info.n_block_id = uint32_t(n_block_id);
			_ASSERTE(n_block_num <= UINT32_MAX);
			m_t_container_info.n_block_num = uint32_t(n_block_num);
			_ASSERTE(n_page_info_num <= UINT32_MAX);
			m_t_container_info.n_page_info_num = uint32_t(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 = int(n_container_width);
			m_t_container_info.n_container_height = int(n_container_height);
			m_t_container_info.n_crc32 = CCrc_32::n_Start();
			m_t_container_info.n_stream_id = n_stream_id;
			_ASSERTE(n_block_id <= UINT32_MAX);
			m_t_container_info.n_block_id = uint32_t(n_block_id);
			_ASSERTE(n_block_num <= UINT32_MAX);
			m_t_container_info.n_block_num = uint32_t(n_block_num);
			_ASSERTE(n_page_info_num <= UINT32_MAX);
			m_t_container_info.n_page_info_num = uint32_t(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)) ||
				   (n_block_space >= sizeof(TPageInfo) && (*p_page_it).r_ItemList().empty())) {
					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;
				_ASSERTE(r_t_glyphs.n_page_index <= UINT32_MAX);
				t_info.n_page_id = uint32_t(r_t_glyphs.n_page_index);
				_ASSERTE(r_t_glyphs.n_last - r_t_glyphs.n_first >= 0 &&
					size_t(r_t_glyphs.n_last - r_t_glyphs.n_first) <= UINT32_MAX);
				t_info.n_glyph_num = uint32_t(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;
	_ASSERTE(n_unicode_version_id <= INT_MAX);
	m_n_unicode_version_id = int(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_FontAntialiasing(bool b_enable_antialiasing)
{
	b_antialias_fonts = b_enable_antialiasing;
}

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

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

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

void CBitmapFont::Set_GlyphGeometryPadding(size_t n_geom_padding)
{
	if(n_geom_padding >= 32)
		return;
	_ASSERTE(n_geom_padding < UINT16_MAX);
	m_t_font_info.n_glyph_geom_padding = uint16_t(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();
	Set_FontAntialiasing();
}

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 = b_antialias_fonts;
	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; // !!
	size_t n_font_face_name_length = strlen(p_s_font_face);
	if(n_font_face_name_length > UINT8_MAX) {
		if(b_verbose)
			fprintf(stderr, "error: font face name is too long to store (" PRIsize ")\n", n_font_face_name_length);
		// if this happends then we could still write a trimmed name or use an extension block
		// (did not happen so far though, font names are usually short; still, I could have spent one more byte on this)
		return false;
	}
	_ASSERTE(n_font_face_name_length <= UINT8_MAX);
	m_t_font_info.n_font_face_length = uint8_t(n_font_face_name_length);
	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

	_ASSERTE(n_box_padding < INT_MAX && n_page_padding < INT_MAX / 2);
	int n_page_resize = int(n_box_padding) - 2 * int(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); // this needs to contain all the glyphs that will be rendered and should know about the glyphs that will not (to calculate area and better estimate the needed number of pages) 
	// prepare metadata block layout

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

	// todo - to support kerning, we would need to fit the kerning table in the first page as an extension block;
	// alternatively we would need to change the format (if doing that, extend font name to uint16_t and also add
	// a variable length extra info after each glyph)
	if(gr.b_SupportsKerning())
		printf("note: the font supports kerning\n"); // see if we have such fonts
	// todo - see if it is easy to get kerning info from GetCharacterPlacement()

	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)) { // this just needs the glyphs with unique bitmaps; note that glyph_info_list is reordered inside!
			if(b_verbose)
				fprintf(stderr, "error: Build_GlyphLayout() failed\n");
			return false;
		}
		// create the final page layout

		// todo - go through the glyphs that will just reference images of other glyphs and copy the coordinates
		// the list have been reordered so we need to look glyphs up by their UTF32 code (should make sure they are unique)

		{
			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 = int16_t(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) {
				size_t 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.empty())? 0 : &glyph_info_list.front();
				TGlyphInfo *p_dst_list_base = (m_glyph_list.empty())? 0 : (TGlyphInfo*)&m_glyph_list.front();
				// 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 " PRIsize " glyphs (excluding " PRIsize " discarded), " PRIsize " 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;
	_ASSERTE(t_raster_info.n_height <= INT_MAX && t_raster_info.n_width < INT_MAX);
	t_bitmap.n_width = int((n_angle & 1)? t_raster_info.n_height : t_raster_info.n_width);
	t_bitmap.n_height = int((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 its 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

			// todo - hash the character bitmaps and look for identical ones, make sure they use the same glyph in the bitmap

			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

	_ASSERTE(n_box_padding < INT_MAX && n_page_padding < INT_MAX / 2);
	const int n_page_resize = int(n_box_padding) - 2 * int(n_page_padding);
	const int n_box_offset = int(n_page_padding);
	const int n_box_resize = int(n_box_padding);
	const 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

	_ASSERTE(ptrdiff_t(n_max_page_size) >= -n_page_resize &&
		(n_page_resize < 0 || n_max_page_size < SIZE_MAX - n_page_resize));
	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];
		_ASSERTE(r_t_glyph.n_bitmap_width <= UINT32_MAX - n_box_padding);
		r_t_glyph.n_bitmap_width += uint32_t(n_box_padding);
		_ASSERTE(r_t_glyph.n_bitmap_height <= UINT32_MAX - n_box_padding);
		r_t_glyph.n_bitmap_height += uint32_t(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 {
					_ASSERTE(n_page_size_padd <= UINT32_MAX);
					page_list.push_back(CBitmapFontPage(uint32_t(n_page_size_padd),
						uint32_t(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;
				_ASSERTE(meta_layout.n_MetaBlock_Width(i) <= UINT32_MAX &&
					meta_layout.n_MetaBlock_Height(i) <= UINT32_MAX);
				t_container_block.n_bitmap_width = uint32_t(meta_layout.n_MetaBlock_Width(i));
				t_container_block.n_bitmap_height = uint32_t(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

		_ASSERTE(n_page_size_padd <= UINT32_MAX);
		if(!CBitmapFontBPSolver::Best_Fit(page_list,
		   glyph_info_list, CBitmapFontBPSolver::CBasicPageFactory(
		   uint32_t(n_page_size_padd), uint32_t(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 " PRIsize " pages, " PRIsize " 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

				_ASSERTE(!b_alloc_meta_blocks || i >= meta_layout.n_MetaBlock_Num() ||
					(meta_layout.n_MetaBlock_Width(i) <= UINT32_MAX &&
					meta_layout.n_MetaBlock_Height(i) <= UINT32_MAX));
				uint32_t n_container_block_width = (b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())?
					uint32_t(meta_layout.n_MetaBlock_Width(i)) : 0;
				uint32_t n_container_block_height = (b_alloc_meta_blocks && i < meta_layout.n_MetaBlock_Num())?
					uint32_t(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 {
						_ASSERTE(n_new_width_padd <= UINT32_MAX && n_new_height_padd <= UINT32_MAX);
						page_list.push_back(CBitmapFontPage(uint32_t(n_new_width_padd), uint32_t(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 " PRIsize " 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

		_ASSERTE(!b_alloc_meta_blocks || i >= meta_layout.n_MetaBlock_Num() ||
			(meta_layout.n_MetaBlock_Width(i) <= UINT32_MAX &&
			meta_layout.n_MetaBlock_Height(i) <= UINT32_MAX));
		uint32_t n_container_block_width = (b_alloc_meta_blocks &&
			i < meta_layout.n_MetaBlock_Num())? uint32_t(meta_layout.n_MetaBlock_Width(i)) : 0;
		uint32_t n_container_block_height = (b_alloc_meta_blocks &&
			i < meta_layout.n_MetaBlock_Num())? uint32_t(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 ===
 */
