summary refs log tree commit diff stats
path: root/libs/cocos2d/CCTextureAtlas.h
blob: f70bb54fc55f195f35cdb8b45a772cef397d5446 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
 * cocos2d for iPhone: http://www.cocos2d-iphone.org
 *
 * Copyright (c) 2008-2010 Ricardo Quesada
 * Copyright (c) 2011 Zynga Inc.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 */

#import "CCTexture2D.h"
#import "ccTypes.h"
#import "ccConfig.h"

/** A class that implements a Texture Atlas.
 Supported features:
   * The atlas file can be a PVRTC, PNG or any other fomrat supported by Texture2D
   * Quads can be udpated in runtime
   * Quads can be added in runtime
   * Quads can be removed in runtime
   * Quads can be re-ordered in runtime
   * The TextureAtlas capacity can be increased or decreased in runtime
   * OpenGL component: V3F, C4B, T2F.
 The quads are rendered using an OpenGL ES VBO.
 To render the quads using an interleaved vertex array list, you should modify the ccConfig.h file 
 */
@interface CCTextureAtlas : NSObject
{
	NSUInteger			totalQuads_;
	NSUInteger			capacity_;
	ccV3F_C4B_T2F_Quad	*quads_;	// quads to be rendered
	GLushort			*indices_;
	CCTexture2D			*texture_;
#if CC_USES_VBO
	GLuint				buffersVBO_[2]; //0: vertex  1: indices
	BOOL				dirty_; //indicates whether or not the array buffer of the VBO needs to be updated
#endif // CC_USES_VBO
}

/** quantity of quads that are going to be drawn */
@property (nonatomic,readonly) NSUInteger totalQuads;
/** quantity of quads that can be stored with the current texture atlas size */
@property (nonatomic,readonly) NSUInteger capacity;
/** Texture of the texture atlas */
@property (nonatomic,retain) CCTexture2D *texture;
/** Quads that are going to be rendered */
@property (nonatomic,readwrite) ccV3F_C4B_T2F_Quad *quads;

/** creates a TextureAtlas with an filename and with an initial capacity for Quads.
 * The TextureAtlas capacity can be increased in runtime.
 */
+(id) textureAtlasWithFile:(NSString*)file capacity:(NSUInteger)capacity;

/** initializes a TextureAtlas with a filename and with a certain capacity for Quads.
 * The TextureAtlas capacity can be increased in runtime.
 *
 * WARNING: Do not reinitialize the TextureAtlas because it will leak memory (issue #706)
 */
-(id) initWithFile: (NSString*) file capacity:(NSUInteger)capacity;

/** creates a TextureAtlas with a previously initialized Texture2D object, and
 * with an initial capacity for n Quads. 
 * The TextureAtlas capacity can be increased in runtime.
 */
+(id) textureAtlasWithTexture:(CCTexture2D *)tex capacity:(NSUInteger)capacity;

/** initializes a TextureAtlas with a previously initialized Texture2D object, and
 * with an initial capacity for Quads. 
 * The TextureAtlas capacity can be increased in runtime.
 *
 * WARNING: Do not reinitialize the TextureAtlas because it will leak memory (issue #706)
 */
-(id) initWithTexture:(CCTexture2D *)tex capacity:(NSUInteger)capacity;

/** updates a Quad (texture, vertex and color) at a certain index
 * index must be between 0 and the atlas capacity - 1
 @since v0.8
 */
-(void) updateQuad:(ccV3F_C4B_T2F_Quad*)quad atIndex:(NSUInteger)index;

/** Inserts a Quad (texture, vertex and color) at a certain index
 index must be between 0 and the atlas capacity - 1
 @since v0.8
 */
-(void) insertQuad:(ccV3F_C4B_T2F_Quad*)quad atIndex:(NSUInteger)index;

/** Removes the quad that is located at a certain index and inserts it at a new index
 This operation is faster than removing and inserting in a quad in 2 different steps
 @since v0.7.2
*/
-(void) insertQuadFromIndex:(NSUInteger)fromIndex atIndex:(NSUInteger)newIndex;

/** removes a quad at a given index number.
 The capacity remains the same, but the total number of quads to be drawn is reduced in 1
 @since v0.7.2
 */
-(void) removeQuadAtIndex:(NSUInteger) index;

/** removes all Quads.
 The TextureAtlas capacity remains untouched. No memory is freed.
 The total number of quads to be drawn will be 0
 @since v0.7.2
 */
-(void) removeAllQuads;

/** resize the capacity of the CCTextureAtlas.
 * The new capacity can be lower or higher than the current one
 * It returns YES if the resize was successful.
 * If it fails to resize the capacity it will return NO with a new capacity of 0.
 */
-(BOOL) resizeCapacity: (NSUInteger) n;


/** draws n quads
 * n can't be greater than the capacity of the Atlas
 */
-(void) drawNumberOfQuads: (NSUInteger) n;


/** draws n quads from an index (offset).
 n + start can't be greater than the capacity of the atlas
 
 @since v1.0
 */
-(void) drawNumberOfQuads: (NSUInteger) n fromIndex: (NSUInteger) start;

/** draws all the Atlas's Quads
 */
-(void) drawQuads;

@end
d='n688' href='#n688'>688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892
//
//  FontLabelStringDrawing.m
//  FontLabel
//
//  Created by Kevin Ballard on 5/5/09.
//  Copyright © 2009 Zynga Game Networks
//
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

#import "FontLabelStringDrawing.h"
#import "ZFont.h"
#import "ZAttributedStringPrivate.h"

@interface ZFont (ZFontPrivate)
@property (nonatomic, readonly) CGFloat ratio;
@end

#define kUnicodeHighSurrogateStart 0xD800
#define kUnicodeHighSurrogateEnd 0xDBFF
#define kUnicodeHighSurrogateMask kUnicodeHighSurrogateStart
#define kUnicodeLowSurrogateStart 0xDC00
#define kUnicodeLowSurrogateEnd 0xDFFF
#define kUnicodeLowSurrogateMask kUnicodeLowSurrogateStart
#define kUnicodeSurrogateTypeMask 0xFC00
#define UnicharIsHighSurrogate(c) ((c & kUnicodeSurrogateTypeMask) == kUnicodeHighSurrogateMask)
#define UnicharIsLowSurrogate(c) ((c & kUnicodeSurrogateTypeMask) == kUnicodeLowSurrogateMask)
#define ConvertSurrogatePairToUTF32(high, low) ((UInt32)((high - 0xD800) * 0x400 + (low - 0xDC00) + 0x10000))

typedef enum {
	kFontTableFormat4 = 4,
	kFontTableFormat12 = 12,
} FontTableFormat;

typedef struct fontTable {
	NSUInteger retainCount;
	CFDataRef cmapTable;
	FontTableFormat format;
	union {
		struct {
			UInt16 segCountX2;
			UInt16 *endCodes;
			UInt16 *startCodes;
			UInt16 *idDeltas;
			UInt16 *idRangeOffsets;
		} format4;
		struct {
			UInt32 nGroups;
			struct {
				UInt32 startCharCode;
				UInt32 endCharCode;
				UInt32 startGlyphCode;
			} *groups;
		} format12;
	} cmap;
} fontTable;

static FontTableFormat supportedFormats[] = { kFontTableFormat4, kFontTableFormat12 };
static size_t supportedFormatsCount = sizeof(supportedFormats) / sizeof(FontTableFormat);

static fontTable *newFontTable(CFDataRef cmapTable, FontTableFormat format) {
	fontTable *table = (struct fontTable *)malloc(sizeof(struct fontTable));
	table->retainCount = 1;
	table->cmapTable = CFRetain(cmapTable);
	table->format = format;
	return table;
}

static fontTable *retainFontTable(fontTable *table) {
	if (table != NULL) {
		table->retainCount++;
	}
	return table;
}

static void releaseFontTable(fontTable *table) {
	if (table != NULL) {
		if (table->retainCount <= 1) {
			CFRelease(table->cmapTable);
			free(table);
		} else {
			table->retainCount--;
		}
	}
}

static const void *fontTableRetainCallback(CFAllocatorRef allocator, const void *value) {
	return retainFontTable((fontTable *)value);
}

static void fontTableReleaseCallback(CFAllocatorRef allocator, const void *value) {
	releaseFontTable((fontTable *)value);
}

static const CFDictionaryValueCallBacks kFontTableDictionaryValueCallBacks = {
	.version = 0,
	.retain = &fontTableRetainCallback,
	.release = &fontTableReleaseCallback,
	.copyDescription = NULL,
	.equal = NULL
};

// read the cmap table from the font
// we only know how to understand some of the table formats at the moment
static fontTable *readFontTableFromCGFont(CGFontRef font) {
	CFDataRef cmapTable = CGFontCopyTableForTag(font, 'cmap');
	NSCAssert1(cmapTable != NULL, @"CGFontCopyTableForTag returned NULL for 'cmap' tag in font %@",
			   (font ? [(id)CFCopyDescription(font) autorelease] : @"(null)"));
	const UInt8 * const bytes = CFDataGetBytePtr(cmapTable);
	NSCAssert1(OSReadBigInt16(bytes, 0) == 0, @"cmap table for font %@ has bad version number",
			   (font ? [(id)CFCopyDescription(font) autorelease] : @"(null)"));
	UInt16 numberOfSubtables = OSReadBigInt16(bytes, 2);
	const UInt8 *unicodeSubtable = NULL;
	//UInt16 unicodeSubtablePlatformID;
	UInt16 unicodeSubtablePlatformSpecificID;
	FontTableFormat unicodeSubtableFormat;
	const UInt8 * const encodingSubtables = &bytes[4];
	for (UInt16 i = 0; i < numberOfSubtables; i++) {
		const UInt8 * const encodingSubtable = &encodingSubtables[8 * i];
		UInt16 platformID = OSReadBigInt16(encodingSubtable, 0);
		UInt16 platformSpecificID = OSReadBigInt16(encodingSubtable, 2);
		// find the best subtable
		// best is defined by a combination of encoding and format
		// At the moment we only support format 4, so ignore all other format tables
		// We prefer platformID == 0, but we will also accept Microsoft's unicode format
		if (platformID == 0 || (platformID == 3 && platformSpecificID == 1)) {
			BOOL preferred = NO;
			if (unicodeSubtable == NULL) {
				preferred = YES;
			} else if (platformID == 0 && platformSpecificID > unicodeSubtablePlatformSpecificID) {
				preferred = YES;
			}
			if (preferred) {
				UInt32 offset = OSReadBigInt32(encodingSubtable, 4);
				const UInt8 *subtable = &bytes[offset];
				UInt16 format = OSReadBigInt16(subtable, 0);
				for (size_t i = 0; i < supportedFormatsCount; i++) {
					if (format == supportedFormats[i]) {
						if (format >= 8) {
							// the version is a fixed-point
							UInt16 formatFrac = OSReadBigInt16(subtable, 2);
							if (formatFrac != 0) {
								// all the current formats with a Fixed version are always *.0
								continue;
							}
						}
						unicodeSubtable = subtable;
						//unicodeSubtablePlatformID = platformID;
						unicodeSubtablePlatformSpecificID = platformSpecificID;
						unicodeSubtableFormat = format;
						break;
					}
				}
			}
		}
	}
	fontTable *table = NULL;
	if (unicodeSubtable != NULL) {
		table = newFontTable(cmapTable, unicodeSubtableFormat);
		switch (unicodeSubtableFormat) {
			case kFontTableFormat4:
				// subtable format 4
				//UInt16 length = OSReadBigInt16(unicodeSubtable, 2);
				//UInt16 language = OSReadBigInt16(unicodeSubtable, 4);
				table->cmap.format4.segCountX2 = OSReadBigInt16(unicodeSubtable, 6);
				//UInt16 searchRange = OSReadBigInt16(unicodeSubtable, 8);
				//UInt16 entrySelector = OSReadBigInt16(unicodeSubtable, 10);
				//UInt16 rangeShift = OSReadBigInt16(unicodeSubtable, 12);
				table->cmap.format4.endCodes = (UInt16*)&unicodeSubtable[14];
				table->cmap.format4.startCodes = (UInt16*)&((UInt8*)table->cmap.format4.endCodes)[table->cmap.format4.segCountX2+2];
				table->cmap.format4.idDeltas = (UInt16*)&((UInt8*)table->cmap.format4.startCodes)[table->cmap.format4.segCountX2];
				table->cmap.format4.idRangeOffsets = (UInt16*)&((UInt8*)table->cmap.format4.idDeltas)[table->cmap.format4.segCountX2];
				//UInt16 *glyphIndexArray = &idRangeOffsets[segCountX2];
				break;
			case kFontTableFormat12:
				table->cmap.format12.nGroups = OSReadBigInt32(unicodeSubtable, 12);
				table->cmap.format12.groups = (void *)&unicodeSubtable[16];
				break;
			default:
				releaseFontTable(table);
				table = NULL;
		}
	}
	CFRelease(cmapTable);
	return table;
}

// outGlyphs must be at least size n
static void mapCharactersToGlyphsInFont(const fontTable *table, unichar characters[], size_t charLen, CGGlyph outGlyphs[], size_t *outGlyphLen) {
	if (table != NULL) {
		NSUInteger j = 0;
		switch (table->format) {
			case kFontTableFormat4: {
				for (NSUInteger i = 0; i < charLen; i++, j++) {
					unichar c = characters[i];
					UInt16 segOffset;
					BOOL foundSegment = NO;
					for (segOffset = 0; segOffset < table->cmap.format4.segCountX2; segOffset += 2) {
						UInt16 endCode = OSReadBigInt16(table->cmap.format4.endCodes, segOffset);
						if (endCode >= c) {
							foundSegment = YES;
							break;
						}
					}
					if (!foundSegment) {
						// no segment
						// this is an invalid font
						outGlyphs[j] = 0;
					} else {
						UInt16 startCode = OSReadBigInt16(table->cmap.format4.startCodes, segOffset);
						if (!(startCode <= c)) {
							// the code falls in a hole between segments
							outGlyphs[j] = 0;
						} else {
							UInt16 idRangeOffset = OSReadBigInt16(table->cmap.format4.idRangeOffsets, segOffset);
							if (idRangeOffset == 0) {
								UInt16 idDelta = OSReadBigInt16(table->cmap.format4.idDeltas, segOffset);
								outGlyphs[j] = (c + idDelta) % 65536;
							} else {
								// use the glyphIndexArray
								UInt16 glyphOffset = idRangeOffset + 2 * (c - startCode);
								outGlyphs[j] = OSReadBigInt16(&((UInt8*)table->cmap.format4.idRangeOffsets)[segOffset], glyphOffset);
							}
						}
					}
				}
				break;
			}
			case kFontTableFormat12: {
				UInt32 lastSegment = UINT32_MAX;
				for (NSUInteger i = 0; i < charLen; i++, j++) {
					unichar c = characters[i];
					UInt32 c32 = c;
					if (UnicharIsHighSurrogate(c)) {
						if (i+1 < charLen) { // do we have another character after this one?
							unichar cc = characters[i+1];
							if (UnicharIsLowSurrogate(cc)) {
								c32 = ConvertSurrogatePairToUTF32(c, cc);
								i++;
							}
						}
					}
					// Start the heuristic search
					// If this is an ASCII char, just do a linear search
					// Otherwise do a hinted, modified binary search
					// Start the first pivot at the last range found
					// And when moving the pivot, limit the movement by increasing
					// powers of two. This should help with locality
					__typeof__(table->cmap.format12.groups[0]) *foundGroup = NULL;
					if (c32 <= 0x7F) {
						// ASCII
						for (UInt32 idx = 0; idx < table->cmap.format12.nGroups; idx++) {
							__typeof__(table->cmap.format12.groups[idx]) *group = &table->cmap.format12.groups[idx];
							if (c32 < OSSwapBigToHostInt32(group->startCharCode)) {
								// we've fallen into a hole
								break;
							} else if (c32 <= OSSwapBigToHostInt32(group->endCharCode)) {
								// this is the range
								foundGroup = group;
								break;
							}
						}
					} else {
						// heuristic search
						UInt32 maxJump = (lastSegment == UINT32_MAX ? UINT32_MAX / 2 : 8);
						UInt32 lowIdx = 0, highIdx = table->cmap.format12.nGroups; // highIdx is the first invalid idx
						UInt32 pivot = (lastSegment == UINT32_MAX ? lowIdx + (highIdx - lowIdx) / 2 : lastSegment);
						while (highIdx > lowIdx) {
							__typeof__(table->cmap.format12.groups[pivot]) *group = &table->cmap.format12.groups[pivot];
							if (c32 < OSSwapBigToHostInt32(group->startCharCode)) {
								highIdx = pivot;
							} else if (c32 > OSSwapBigToHostInt32(group->endCharCode)) {
								lowIdx = pivot + 1;
							} else {
								// we've hit the range
								foundGroup = group;
								break;
							}
							if (highIdx - lowIdx > maxJump * 2) {
								if (highIdx == pivot) {
									pivot -= maxJump;
								} else {
									pivot += maxJump;
								}
								maxJump *= 2;
							} else {
								pivot = lowIdx + (highIdx - lowIdx) / 2;
							}
						}
						if (foundGroup != NULL) lastSegment = pivot;
					}
					if (foundGroup == NULL) {
						outGlyphs[j] = 0;
					} else {
						outGlyphs[j] = (CGGlyph)(OSSwapBigToHostInt32(foundGroup->startGlyphCode) +
												 (c32 - OSSwapBigToHostInt32(foundGroup->startCharCode)));
					}
				}
				break;
			}
		}
		if (outGlyphLen != NULL) *outGlyphLen = j;
	} else {
		// we have no table, so just null out the glyphs
		bzero(outGlyphs, charLen*sizeof(CGGlyph));
		if (outGlyphLen != NULL) *outGlyphLen = 0;
	}
}

static BOOL mapGlyphsToAdvancesInFont(ZFont *font, size_t n, CGGlyph glyphs[], CGFloat outAdvances[]) {
	int advances[n];
	if (CGFontGetGlyphAdvances(font.cgFont, glyphs, n, advances)) {
		CGFloat ratio = font.ratio;
		
		for (size_t i = 0; i < n; i++) {
			outAdvances[i] = advances[i]*ratio;
		}
		return YES;
	} else {
		bzero(outAdvances, n*sizeof(CGFloat));
	}
	return NO;
}

static id getValueOrDefaultForRun(ZAttributeRun *run, NSString *key) {
	id value = [run.attributes objectForKey:key];
	if (value == nil) {
		static NSDictionary *defaultValues = nil;
		if (defaultValues == nil) {
			defaultValues = [[NSDictionary alloc] initWithObjectsAndKeys:
							 [ZFont fontWithUIFont:[UIFont systemFontOfSize:12]], ZFontAttributeName,
							 [UIColor blackColor], ZForegroundColorAttributeName,
							 [UIColor clearColor], ZBackgroundColorAttributeName,
							 [NSNumber numberWithInt:ZUnderlineStyleNone], ZUnderlineStyleAttributeName,
							 nil];
		}
		value = [defaultValues objectForKey:key];
	}
	return value;
}

static void readRunInformation(NSArray *attributes, NSUInteger len, CFMutableDictionaryRef fontTableMap,
							   NSUInteger index, ZAttributeRun **currentRun, NSUInteger *nextRunStart,
							   ZFont **currentFont, fontTable **currentTable) {
	*currentRun = [attributes objectAtIndex:index];
	*nextRunStart = ([attributes count] > index+1 ? [[attributes objectAtIndex:index+1] index] : len);
	*currentFont = getValueOrDefaultForRun(*currentRun, ZFontAttributeName);
	if (!CFDictionaryGetValueIfPresent(fontTableMap, (*currentFont).cgFont, (const void **)currentTable)) {
		*currentTable = readFontTableFromCGFont((*currentFont).cgFont);
		CFDictionarySetValue(fontTableMap, (*currentFont).cgFont, *currentTable);
		releaseFontTable(*currentTable);
	}
}

static CGSize drawOrSizeTextConstrainedToSize(BOOL performDraw, NSString *string, NSArray *attributes, CGSize constrainedSize, NSUInteger maxLines,
											  UILineBreakMode lineBreakMode, UITextAlignment alignment, BOOL ignoreColor) {
	NSUInteger len = [string length];
	NSUInteger idx = 0;
	CGPoint drawPoint = CGPointZero;
	CGSize retValue = CGSizeZero;
	CGContextRef ctx = (performDraw ? UIGraphicsGetCurrentContext() : NULL);
	
	BOOL convertNewlines = (maxLines == 1);
	
	// Extract the characters from the string
	// Convert newlines to spaces if necessary
	unichar *characters = (unichar *)malloc(sizeof(unichar) * len);
	if (convertNewlines) {
		NSCharacterSet *charset = [NSCharacterSet newlineCharacterSet];
		NSRange range = NSMakeRange(0, len);
		size_t cIdx = 0;
		while (range.length > 0) {
			NSRange newlineRange = [string rangeOfCharacterFromSet:charset options:0 range:range];
			if (newlineRange.location == NSNotFound) {
				[string getCharacters:&characters[cIdx] range:range];
				cIdx += range.length;
				break;
			} else {
				NSUInteger delta = newlineRange.location - range.location;
				if (newlineRange.location > range.location) {
					[string getCharacters:&characters[cIdx] range:NSMakeRange(range.location, delta)];
				}
				cIdx += delta;
				characters[cIdx] = (unichar)' ';
				cIdx++;
				delta += newlineRange.length;
				range.location += delta, range.length -= delta;
				if (newlineRange.length == 1 && range.length >= 1 &&
					[string characterAtIndex:newlineRange.location] == (unichar)'\r' &&
					[string characterAtIndex:range.location] == (unichar)'\n') {
					// CRLF sequence, skip the LF
					range.location += 1, range.length -= 1;
				}
			}
		}
		len = cIdx;
	} else {
		[string getCharacters:characters range:NSMakeRange(0, len)];
	}
	
	// Create storage for glyphs and advances
	CGGlyph *glyphs;
	CGFloat *advances;
	{
		NSUInteger maxRunLength = 0;
		ZAttributeRun *a = [attributes objectAtIndex:0];
		for (NSUInteger i = 1; i < [attributes count]; i++) {
			ZAttributeRun *b = [attributes objectAtIndex:i];
			maxRunLength = MAX(maxRunLength, b.index - a.index);
			a = b;
		}
		maxRunLength = MAX(maxRunLength, len - a.index);
		maxRunLength++; // for a potential ellipsis
		glyphs = (CGGlyph *)malloc(sizeof(CGGlyph) * maxRunLength);
		advances = (CGFloat *)malloc(sizeof(CGFloat) * maxRunLength);
	}
	
	// Use this table to cache all fontTable objects
	CFMutableDictionaryRef fontTableMap = CFDictionaryCreateMutable(NULL, 0, &kCFTypeDictionaryKeyCallBacks,
																	 &kFontTableDictionaryValueCallBacks);
	
	// Fetch initial style values
	NSUInteger currentRunIdx = 0;
	ZAttributeRun *currentRun;
	NSUInteger nextRunStart;
	ZFont *currentFont;
	fontTable *currentTable;
	
#define READ_RUN() readRunInformation(attributes, len, fontTableMap, \
									  currentRunIdx, &currentRun, &nextRunStart, \
									  &currentFont, &currentTable)
	
	READ_RUN();
	
	// fetch the glyphs for the first run
	size_t glyphCount;
	NSUInteger glyphIdx;
	
#define READ_GLYPHS() do { \
		mapCharactersToGlyphsInFont(currentTable, &characters[currentRun.index], (nextRunStart - currentRun.index), glyphs, &glyphCount); \
		mapGlyphsToAdvancesInFont(currentFont, (nextRunStart - currentRun.index), glyphs, advances); \
		glyphIdx = 0; \
	} while (0)
	
	READ_GLYPHS();
	
	NSMutableCharacterSet *alphaCharset = [NSMutableCharacterSet alphanumericCharacterSet];
	[alphaCharset addCharactersInString:@"([{'\"\u2019\u02BC"];
	
	// scan left-to-right looking for newlines or until we hit the width constraint
	// When we hit a wrapping point, calculate truncation as follows:
	// If we have room to draw at least one more character on the next line, no truncation
	// Otherwise apply the truncation algorithm to the current line.
	// After calculating any truncation, draw.
	// Each time we hit the end of an attribute run, calculate the new font and make sure
	// it fits (vertically) within the size constraint. If not, truncate this line.
	// When we draw, iterate over the attribute runs for this line and draw each run separately
	BOOL lastLine = NO; // used to indicate truncation and to stop the iterating
	NSUInteger lineCount = 1;
	while (idx < len && !lastLine) {
		if (maxLines > 0 && lineCount == maxLines) {
			lastLine = YES;
		}
		// scan left-to-right
		struct {
			NSUInteger index;
			NSUInteger glyphIndex;
			NSUInteger currentRunIdx;
		} indexCache = { idx, glyphIdx, currentRunIdx };
		CGSize lineSize = CGSizeMake(0, currentFont.leading);
		CGFloat lineAscender = currentFont.ascender;
		struct {
			NSUInteger index;
			NSUInteger glyphIndex;
			NSUInteger currentRunIdx;
			CGSize lineSize;
		} lastWrapCache = {0, 0, 0, CGSizeZero};
		BOOL inAlpha = NO; // used for calculating wrap points
		
		BOOL finishLine = NO;
		for (;idx <= len && !finishLine;) {
			NSUInteger skipCount = 0;
			if (idx == len) {
				finishLine = YES;
				lastLine = YES;
			} else {
				if (idx >= nextRunStart) {
					// cycle the font and table and grab the next set of glyphs
					do {
						currentRunIdx++;
						READ_RUN();
					} while (idx >= nextRunStart);
					READ_GLYPHS();
					// re-scan the characters to synchronize the glyph index
					for (NSUInteger j = currentRun.index; j < idx; j++) {
						if (UnicharIsHighSurrogate(characters[j]) && j+1<len && UnicharIsLowSurrogate(characters[j+1])) {
							j++;
						}
						glyphIdx++;
					}
					if (currentFont.leading > lineSize.height) {
						lineSize.height = currentFont.leading;
						if (retValue.height + currentFont.ascender > constrainedSize.height) {
							lastLine = YES;
							finishLine = YES;
						}
					}
					lineAscender = MAX(lineAscender, currentFont.ascender);
				}
				unichar c = characters[idx];
				// Mark a wrap point before spaces and after any stretch of non-alpha characters
				BOOL markWrap = NO;
				if (c == (unichar)' ') {
					markWrap = YES;
				} else if ([alphaCharset characterIsMember:c]) {
					if (!inAlpha) {
						markWrap = YES;
						inAlpha = YES;
					}
				} else {
					inAlpha = NO;
				}
				if (markWrap) {
					lastWrapCache = (__typeof__(lastWrapCache)){
						.index = idx,
						.glyphIndex = glyphIdx,
						.currentRunIdx = currentRunIdx,
						.lineSize = lineSize
					};
				}
				// process the line
				if (c == (unichar)'\n' || c == 0x0085) { // U+0085 is the NEXT_LINE unicode character
					finishLine = YES;
					skipCount = 1;
				} else if (c == (unichar)'\r') {
					finishLine = YES;
					// check for CRLF
					if (idx+1 < len && characters[idx+1] == (unichar)'\n') {
						skipCount = 2;
					} else {
						skipCount = 1;
					}
				} else if (lineSize.width + advances[glyphIdx] > constrainedSize.width) {
					finishLine = YES;
					if (retValue.height + lineSize.height + currentFont.ascender > constrainedSize.height) {
						lastLine = YES;
					}
					// walk backwards if wrapping is necessary
					if (lastWrapCache.index > indexCache.index && lineBreakMode != UILineBreakModeCharacterWrap &&
						(!lastLine || lineBreakMode != UILineBreakModeClip)) {
						// we're doing some sort of word wrapping
						idx = lastWrapCache.index;
						lineSize = lastWrapCache.lineSize;
						if (!lastLine) {
							// re-check if this is the last line
							if (lastWrapCache.currentRunIdx != currentRunIdx) {
								currentRunIdx = lastWrapCache.currentRunIdx;
								READ_RUN();
								READ_GLYPHS();
							}
							if (retValue.height + lineSize.height + currentFont.ascender > constrainedSize.height) {
								lastLine = YES;
							}
						}
						glyphIdx = lastWrapCache.glyphIndex;
						// skip any spaces
						for (NSUInteger j = idx; j < len && characters[j] == (unichar)' '; j++) {
							skipCount++;
						}
					}
				}
			}
			if (finishLine) {
				// TODO: support head/middle truncation
				if (lastLine && idx < len && lineBreakMode == UILineBreakModeTailTruncation) {
					// truncate
					unichar ellipsis = 0x2026; // ellipsis (…)
					CGGlyph ellipsisGlyph;
					mapCharactersToGlyphsInFont(currentTable, &ellipsis, 1, &ellipsisGlyph, NULL);
					CGFloat ellipsisWidth;
					mapGlyphsToAdvancesInFont(currentFont, 1, &ellipsisGlyph, &ellipsisWidth);
					while ((idx - indexCache.index) > 1 && lineSize.width + ellipsisWidth > constrainedSize.width) {
						// we have more than 1 character and we're too wide, so back up
						idx--;
						if (UnicharIsHighSurrogate(characters[idx]) && UnicharIsLowSurrogate(characters[idx+1])) {
							idx--;
						}
						if (idx < currentRun.index) {
							ZFont *oldFont = currentFont;
							do {
								currentRunIdx--;
								READ_RUN();
							} while (idx < currentRun.index);
							READ_GLYPHS();
							glyphIdx = glyphCount-1;
							if (oldFont != currentFont) {
								mapCharactersToGlyphsInFont(currentTable, &ellipsis, 1, &ellipsisGlyph, NULL);
								mapGlyphsToAdvancesInFont(currentFont, 1, &ellipsisGlyph, &ellipsisWidth);
							}
						} else {
							glyphIdx--;
						}
						lineSize.width -= advances[glyphIdx];
					}
					// skip any spaces before truncating
					while ((idx - indexCache.index) > 1 && characters[idx-1] == (unichar)' ') {
						idx--;
						if (idx < currentRun.index) {
							currentRunIdx--;
							READ_RUN();
							READ_GLYPHS();
							glyphIdx = glyphCount-1;
						} else {
							glyphIdx--;
						}
						lineSize.width -= advances[glyphIdx];
					}
					lineSize.width += ellipsisWidth;
					glyphs[glyphIdx] = ellipsisGlyph;
					idx++;
					glyphIdx++;
				}
				retValue.width = MAX(retValue.width, lineSize.width);
				retValue.height += lineSize.height;
				
				// draw
				if (performDraw) {
					switch (alignment) {
						case UITextAlignmentLeft:
							drawPoint.x = 0;
							break;
						case UITextAlignmentCenter:
							drawPoint.x = (constrainedSize.width - lineSize.width) / 2.0f;
							break;
						case UITextAlignmentRight:
							drawPoint.x = constrainedSize.width - lineSize.width;
							break;
					}
					NSUInteger stopGlyphIdx = glyphIdx;
					NSUInteger lastRunIdx = currentRunIdx;
					NSUInteger stopCharIdx = idx;
					idx = indexCache.index;
					if (currentRunIdx != indexCache.currentRunIdx) {
						currentRunIdx = indexCache.currentRunIdx;
						READ_RUN();
						READ_GLYPHS();
					}
					glyphIdx = indexCache.glyphIndex;
					for (NSUInteger drawIdx = currentRunIdx; drawIdx <= lastRunIdx; drawIdx++) {
						if (drawIdx != currentRunIdx) {
							currentRunIdx = drawIdx;
							READ_RUN();
							READ_GLYPHS();
						}
						NSUInteger numGlyphs;
						if (drawIdx == lastRunIdx) {
							numGlyphs = stopGlyphIdx - glyphIdx;
							idx = stopCharIdx;
						} else {
							numGlyphs = glyphCount - glyphIdx;
							idx = nextRunStart;
						}
						CGContextSetFont(ctx, currentFont.cgFont);
						CGContextSetFontSize(ctx, currentFont.pointSize);
						// calculate the fragment size
						CGFloat fragmentWidth = 0;
						for (NSUInteger g = 0; g < numGlyphs; g++) {
							fragmentWidth += advances[glyphIdx + g];
						}
						
						if (!ignoreColor) {
							UIColor *foregroundColor = getValueOrDefaultForRun(currentRun, ZForegroundColorAttributeName);
							UIColor *backgroundColor = getValueOrDefaultForRun(currentRun, ZBackgroundColorAttributeName);
							if (backgroundColor != nil && ![backgroundColor isEqual:[UIColor clearColor]]) {
								[backgroundColor setFill];
								UIRectFillUsingBlendMode((CGRect){ drawPoint, { fragmentWidth, lineSize.height } }, kCGBlendModeNormal);
							}
							[foregroundColor setFill];
						}
						
						CGContextShowGlyphsAtPoint(ctx, drawPoint.x, drawPoint.y + lineAscender, &glyphs[glyphIdx], numGlyphs);
						NSNumber *underlineStyle = getValueOrDefaultForRun(currentRun, ZUnderlineStyleAttributeName);
						if ([underlineStyle	integerValue] & ZUnderlineStyleMask) {
							// we only support single for the time being
							UIRectFill(CGRectMake(drawPoint.x, drawPoint.y + lineAscender, fragmentWidth, 1));
						}
						drawPoint.x += fragmentWidth;
						glyphIdx += numGlyphs;
					}
					drawPoint.y += lineSize.height;
				}
				idx += skipCount;
				glyphIdx += skipCount;
				lineCount++;
			} else {
				lineSize.width += advances[glyphIdx];
				glyphIdx++;
				idx++;
				if (idx < len && UnicharIsHighSurrogate(characters[idx-1]) && UnicharIsLowSurrogate(characters[idx])) {
					// skip the second half of the surrogate pair
					idx++;
				}
			}
		}
	}
	CFRelease(fontTableMap);
	free(glyphs);
	free(advances);
	free(characters);
	
#undef READ_GLYPHS
#undef READ_RUN
	
	return retValue;
}

static NSArray *attributeRunForFont(ZFont *font) {
	return [NSArray arrayWithObject:[ZAttributeRun attributeRunWithIndex:0
															  attributes:[NSDictionary dictionaryWithObject:font
																									 forKey:ZFontAttributeName]]];
}

static CGSize drawTextInRect(CGRect rect, NSString *text, NSArray *attributes, UILineBreakMode lineBreakMode,
							 UITextAlignment alignment, NSUInteger numberOfLines, BOOL ignoreColor) {
	CGContextRef ctx = UIGraphicsGetCurrentContext();
	
	CGContextSaveGState(ctx);
	
	// flip it upside-down because our 0,0 is upper-left, whereas ttfs are for screens where 0,0 is lower-left
	CGAffineTransform textTransform = CGAffineTransformMake(1.0f, 0.0f, 0.0f, -1.0f, 0.0f, 0.0f);
	CGContextSetTextMatrix(ctx, textTransform);
	
	CGContextTranslateCTM(ctx, rect.origin.x, rect.origin.y);
	
	CGContextSetTextDrawingMode(ctx, kCGTextFill);
	CGSize size = drawOrSizeTextConstrainedToSize(YES, text, attributes, rect.size, numberOfLines, lineBreakMode, alignment, ignoreColor);
	
	CGContextRestoreGState(ctx);
	
	return size;
}

@implementation NSString (FontLabelStringDrawing)
// CGFontRef-based methods
- (CGSize)sizeWithCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize {
	return [self sizeWithZFont:[ZFont fontWithCGFont:font size:pointSize]];
}

- (CGSize)sizeWithCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize constrainedToSize:(CGSize)size {
	return [self sizeWithZFont:[ZFont fontWithCGFont:font size:pointSize] constrainedToSize:size];
}

- (CGSize)sizeWithCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize constrainedToSize:(CGSize)size
		   lineBreakMode:(UILineBreakMode)lineBreakMode {
	return [self sizeWithZFont:[ZFont fontWithCGFont:font size:pointSize] constrainedToSize:size lineBreakMode:lineBreakMode];
}

- (CGSize)drawAtPoint:(CGPoint)point withCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize {
	return [self drawAtPoint:point withZFont:[ZFont fontWithCGFont:font size:pointSize]];
}

- (CGSize)drawInRect:(CGRect)rect withCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize {
	return [self drawInRect:rect withZFont:[ZFont fontWithCGFont:font size:pointSize]];
}

- (CGSize)drawInRect:(CGRect)rect withCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize lineBreakMode:(UILineBreakMode)lineBreakMode {
	return [self drawInRect:rect withZFont:[ZFont fontWithCGFont:font size:pointSize] lineBreakMode:lineBreakMode];
}

- (CGSize)drawInRect:(CGRect)rect withCGFont:(CGFontRef)font pointSize:(CGFloat)pointSize
	   lineBreakMode:(UILineBreakMode)lineBreakMode alignment:(UITextAlignment)alignment {
	return [self drawInRect:rect withZFont:[ZFont fontWithCGFont:font size:pointSize] lineBreakMode:lineBreakMode alignment:alignment];
}

// ZFont-based methods
- (CGSize)sizeWithZFont:(ZFont *)font {
	CGSize size = drawOrSizeTextConstrainedToSize(NO, self, attributeRunForFont(font), CGSizeMake(CGFLOAT_MAX, CGFLOAT_MAX), 1,
												  UILineBreakModeClip, UITextAlignmentLeft, YES);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)sizeWithZFont:(ZFont *)font constrainedToSize:(CGSize)size {
	return [self sizeWithZFont:font constrainedToSize:size lineBreakMode:UILineBreakModeWordWrap];
}

/*
 According to experimentation with UIStringDrawing, this can actually return a CGSize whose height is greater
 than the one passed in. The two cases are as follows:
 1. If the given size parameter's height is smaller than a single line, the returned value will
 be the height of one line.
 2. If the given size parameter's height falls between multiples of a line height, and the wrapped string
 actually extends past the size.height, and the difference between size.height and the previous multiple
 of a line height is >= the font's ascender, then the returned size's height is extended to the next line.
 To put it simply, if the baseline point of a given line falls in the given size, the entire line will
 be present in the output size.
 */
- (CGSize)sizeWithZFont:(ZFont *)font constrainedToSize:(CGSize)size lineBreakMode:(UILineBreakMode)lineBreakMode {
	size = drawOrSizeTextConstrainedToSize(NO, self, attributeRunForFont(font), size, 0, lineBreakMode, UITextAlignmentLeft, YES);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)sizeWithZFont:(ZFont *)font constrainedToSize:(CGSize)size lineBreakMode:(UILineBreakMode)lineBreakMode
		  numberOfLines:(NSUInteger)numberOfLines {
	size = drawOrSizeTextConstrainedToSize(NO, self, attributeRunForFont(font), size, numberOfLines, lineBreakMode, UITextAlignmentLeft, YES);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)drawAtPoint:(CGPoint)point withZFont:(ZFont *)font {
	return [self drawAtPoint:point forWidth:CGFLOAT_MAX withZFont:font lineBreakMode:UILineBreakModeClip];
}

- (CGSize)drawAtPoint:(CGPoint)point forWidth:(CGFloat)width withZFont:(ZFont *)font lineBreakMode:(UILineBreakMode)lineBreakMode {
	return drawTextInRect((CGRect){ point, { width, CGFLOAT_MAX } }, self, attributeRunForFont(font), lineBreakMode, UITextAlignmentLeft, 1, YES);
}

- (CGSize)drawInRect:(CGRect)rect withZFont:(ZFont *)font {
	return [self drawInRect:rect withZFont:font lineBreakMode:UILineBreakModeWordWrap];
}

- (CGSize)drawInRect:(CGRect)rect withZFont:(ZFont *)font lineBreakMode:(UILineBreakMode)lineBreakMode {
	return [self drawInRect:rect withZFont:font lineBreakMode:lineBreakMode alignment:UITextAlignmentLeft];
}

- (CGSize)drawInRect:(CGRect)rect withZFont:(ZFont *)font lineBreakMode:(UILineBreakMode)lineBreakMode
		   alignment:(UITextAlignment)alignment {
	return drawTextInRect(rect, self, attributeRunForFont(font), lineBreakMode, alignment, 0, YES);
}

- (CGSize)drawInRect:(CGRect)rect withZFont:(ZFont *)font lineBreakMode:(UILineBreakMode)lineBreakMode
		   alignment:(UITextAlignment)alignment numberOfLines:(NSUInteger)numberOfLines {
	return drawTextInRect(rect, self, attributeRunForFont(font), lineBreakMode, alignment, numberOfLines, YES);
}
@end

@implementation ZAttributedString (ZAttributedStringDrawing)
- (CGSize)size {
	CGSize size = drawOrSizeTextConstrainedToSize(NO, self.string, self.attributes, CGSizeMake(CGFLOAT_MAX, CGFLOAT_MAX), 1,
												  UILineBreakModeClip, UITextAlignmentLeft, NO);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)sizeConstrainedToSize:(CGSize)size {
	return [self sizeConstrainedToSize:size lineBreakMode:UILineBreakModeWordWrap];
}

- (CGSize)sizeConstrainedToSize:(CGSize)size lineBreakMode:(UILineBreakMode)lineBreakMode {
	size = drawOrSizeTextConstrainedToSize(NO, self.string, self.attributes, size, 0, lineBreakMode, UITextAlignmentLeft, NO);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)sizeConstrainedToSize:(CGSize)size lineBreakMode:(UILineBreakMode)lineBreakMode
				  numberOfLines:(NSUInteger)numberOfLines {
	size = drawOrSizeTextConstrainedToSize(NO, self.string, self.attributes, size, numberOfLines, lineBreakMode, UITextAlignmentLeft, NO);
	return CGSizeMake(ceilf(size.width), ceilf(size.height));
}

- (CGSize)drawAtPoint:(CGPoint)point {
	return [self drawAtPoint:point forWidth:CGFLOAT_MAX lineBreakMode:UILineBreakModeClip];
}

- (CGSize)drawAtPoint:(CGPoint)point forWidth:(CGFloat)width lineBreakMode:(UILineBreakMode)lineBreakMode {
	return drawTextInRect((CGRect){ point, { width, CGFLOAT_MAX } }, self.string, self.attributes, lineBreakMode, UITextAlignmentLeft, 1, NO);
}

- (CGSize)drawInRect:(CGRect)rect {
	return [self drawInRect:rect withLineBreakMode:UILineBreakModeWordWrap];
}

- (CGSize)drawInRect:(CGRect)rect withLineBreakMode:(UILineBreakMode)lineBreakMode {
	return [self drawInRect:rect withLineBreakMode:lineBreakMode alignment:UITextAlignmentLeft];
}

- (CGSize)drawInRect:(CGRect)rect withLineBreakMode:(UILineBreakMode)lineBreakMode alignment:(UITextAlignment)alignment {
	return drawTextInRect(rect, self.string, self.attributes, lineBreakMode, alignment, 0, NO);
}

- (CGSize)drawInRect:(CGRect)rect withLineBreakMode:(UILineBreakMode)lineBreakMode alignment:(UITextAlignment)alignment
	   numberOfLines:(NSUInteger)numberOfLines {
	return drawTextInRect(rect, self.string, self.attributes, lineBreakMode, alignment, numberOfLines, NO);
}
@end