1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* ***** BEGIN LICENSE BLOCK *****
3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 * http://www.mozilla.org/MPL/
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
15 * The Original Code is Mozilla Communicator client code.
17 * The Initial Developer of the Original Code is
18 * Netscape Communications Corporation.
19 * Portions created by the Initial Developer are Copyright (C) 2001
20 * the Initial Developer. All Rights Reserved.
23 * Brian Stell <bstell@netscape.com>
25 * Alternatively, the contents of this file may be used under the terms of
26 * either of the GNU General Public License Version 2 or later (the "GPL"),
27 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28 * in which case the provisions of the GPL or the LGPL are applicable instead
29 * of those above. If you wish to allow use of your version of this file only
30 * under the terms of either the GPL or the LGPL, and not to allow others to
31 * use your version of this file under the terms of the MPL, indicate your
32 * decision by deleting the provisions above and replace them with the notice
33 * and other provisions required by the GPL or the LGPL. If you do not delete
34 * the provisions above, a recipient may use your version of this file under
35 * the terms of any one of the MPL, the GPL or the LGPL.
37 * ***** END LICENSE BLOCK ***** */
39 #ifndef NSCOMPRESSEDCHARMAP_H
40 #define NSCOMPRESSEDCHARMAP_H
42 #include "nsICharRepresentable.h"
44 #define ALU_SIZE PR_BITS_PER_LONG
49 # define ALU_TYPE PRUint32
50 # define CCMAP_POW2(n) (1L<<(n))
51 # define CCMAP_BITS_PER_ALU_LOG2 5
53 # define ALU_TYPE PRUint64
54 # define CCMAP_POW2(n) (1L<<(n))
55 # define CCMAP_BITS_PER_ALU_LOG2 6
57 # define ALU_TYPE PRUint16
58 # define CCMAP_POW2(n) (1<<(n))
59 # define CCMAP_BITS_PER_ALU_LOG2 4
63 class nsICharRepresentable;
65 extern PRUint16* CreateEmptyCCMap();
66 extern PRUint16* MapToCCMap(PRUint32* aMap);
67 extern PRUint16* MapperToCCMap(nsICharRepresentable *aMapper);
68 extern void FreeCCMap(PRUint16* &aMap);
69 extern PRBool NextNonEmptyCCMapPage(const PRUint16 *, PRUint32 *);
70 extern PRBool IsSameCCMap(PRUint16* ccmap1, PRUint16* ccmap2);
72 void printCCMap(PRUint16* aCCMap);
76 // surrogate support extension
78 MapToCCMapExt(PRUint32* aBmpPlaneMap, PRUint32** aOtherPlaneMaps, PRUint32 aOtherPlaneNum);
81 // nsCompressedCharMap
83 // A Compressed Char Map (CCMap) saves memory by folding all
84 // the empty portions of the map on top of each other.
86 // Building a Compressed Char Map (CCMap) is more complex than
87 // accessing it. We use the nsCompressedCharMap object to
88 // build the CCMap. Once nsCompressedCharMap has built the CCMap
89 // we get a copy of the CCMap and discard the nsCompressedCharMap
90 // object. The CCMap is an array of PRUint16 and is accessed by
93 // See "Character Map Compression" below for a discussion of
94 // what the array looks like.
97 // The maximum size a CCMap:
98 // (16 upper pointers) + (16 empty mid pointers) +
99 // (16 empty page) + (16*16 max mid pointers) +
100 // (256*16 max pages) = 4400 PRUint16
101 #define CCMAP_MAX_LEN (16+16+16+256+4096)
103 // non-bmp unicode support extension
104 #define EXTENDED_UNICODE_PLANES 16
106 class nsCompressedCharMap {
108 nsCompressedCharMap();
109 ~nsCompressedCharMap();
111 PRUint16* NewCCMap();
112 PRUint16* FillCCMap(PRUint16* aCCMap);
113 PRUint16 GetSize() {return mUsedLen;};
114 void SetChar(PRUint32);
115 void SetChars(PRUint16*);
116 void SetChars(PRUint16, ALU_TYPE*);
117 void SetChars(PRUint32*);
118 void Extend() {mExtended = PR_TRUE;} // enable surrogate area
122 PRUint16 mCCMap[CCMAP_MAX_LEN];
123 ALU_TYPE used_for_align; // do not use; only here to cause
126 PRUint16 mUsedLen; // in PRUint16
127 PRUint16 mAllOnesPage;
131 // for surrogate support
132 PRUint32* mExtMap[EXTENDED_UNICODE_PLANES+1];
133 PRUint32 mMap[UCS2_MAP_LEN];
137 // Character Map Compression
139 // Each font requires its own 8k charmap. On a system with 200
140 // fonts this would take: 200 * 8K = 1600K memory.
142 // Since most char maps are mostly empty a significant amount
143 // of memory can be saved by not allocating the unused sections.
145 // If the map has one or more levels of indirection then the
146 // the empty sections of the map can all be folded to a single
147 // common empty element. In this way only the non-empty sections
148 // need space. Because the empty sections actually point to a
149 // common empty section every entry in the map can be valid
150 // without requiring actually allocating space.
151 // Some larger CJK fonts have large sections where every bit
152 // is set. In the same way that the empty sections are folded
153 // onto one "empty page", the sections where all bits are set are
154 // folded on to one "all bits set page" .
156 // Break up the Unicode range bits 0x0000 - 0xFFFF
157 // into 3 bit ranges:
159 // upper bits: bit15 - bit12
160 // mid bits: bit11 - bit8
161 // page bits: bit7 - bit0
163 // within a page, (assumming a 4 byte ALU)
164 // bits 7-5 select one of the 8 longs
165 // bits 4-0 select one of the 32 bits within the long
167 // There is exactly one upper "pointers" array.
169 // The upper pointers each point to a mid array. If there are no chars
170 // in an upper pointer's block that pointer points to the empty mid.
171 // Thus all upper pointers are "valid" even if they do not have space
172 // allocated; eg: the accessor macro does not need to test if the
175 // Each mid pointer in the mid array points to a page. If there are no
176 // chars in a mid pointer's page that pointer points to the empty page.
177 // Thus all mid pointers are "valid" even if they do not have space
178 // allocated; eg: the accessor macro does not need to test if the
181 // Since the array will be less than 5K PRUint16 the "pointers" can
182 // be implemented as 2 byte offsets from the base instead of
185 // the format of the CCMap is
186 // the upper pointers (16 PRUint16)
187 // the empty mid pointers (16 PRUint16)
188 // the empty page (16 PRUint16)
189 // non-empty mid pointers and pages as needed
191 // One minor note: for a completely empty map it is actually
192 // possible to fold the upper, empty mid, and empty page
193 // on top of each other and make a map of only 32 bytes.
194 #define CCMAP_EMPTY_SIZE_PER_INT16 16
196 // offsets to the empty mid and empty page
197 #define CCMAP_EMPTY_MID CCMAP_NUM_UPPER_POINTERS
198 #define CCMAP_EMPTY_PAGE CCMAP_EMPTY_MID+CCMAP_NUM_MID_POINTERS
201 // Because the table is offset based the code can build the table in a
202 // temp space (max table size on the stack) and then do one alloc of
203 // the actual needed size and simply copy over the data.
207 // Compressed Char map surrogate extension
209 // The design goal of surrogate support extension is to keep efficiency
210 // and compatibility of existing compressed charmap operations. Most of
211 // existing operation are untouched. For BMP support, very little memory
212 // overhead (4 bytes) is added. Runtime efficiency of BMP support is
215 // structure of extended charmap:
216 // ccmap flag 1 PRUint16 (PRUint32) , indicates if this is extended or not
217 // bmp ccmap size 1 PRUint16 (PRUint32) , the size of BMP ccmap,
218 // BMP ccmap size varies,
219 // plane index 16 PRUint32, use to index ccmap for non-BMP plane
220 // empty ccmap 16 PRUint16, a total empty ccmap
221 // non-BMP ccmaps size varies, other non-empty, non-BMP ccmap
223 // Changes to basic ccmap
224 // 2 PRUint16 (PRUint32 on 64bit machines) are added in the very beginning.
225 // One is used to specify the size
226 // of the ccmap, the other is used as a flag. But these 2 fields are indexed
227 // negatively so that all other operation remain unchanged to keep efficiency.
228 // ccmap memory allocation is moved from nsCompressedCharMap::NewCCMap to
232 // A 16*PRUint32 array was put at the end of basic ccmap, each PRUint32 either
233 // pointed to the empty ccmap or a independent plane ccmap. Directly after this
234 // array is a empty ccmap. All planes that has no character will share this ccmap.
235 // All non-empty plane will have a ccmap.
236 // "MapToCCMapExt" is added to created an extended ccmap, each plane ccmap is
237 // created the same as basic one, but without 2 additional fields.
238 // "HasGlyphExt" is used to access extended ccmap, it first need to locate the
239 // plane ccmap, and then operated the same way as "HasGlyph".
241 // Compatibility between old and new one
242 // Because extended ccmap include an exactly identical basic ccmap in its head,
243 // basic ccmap operation (HasGlyph) can be applied on extended ccmap without
245 // Because basic ccmap is now have a flag to indicate if it is a extended one,
246 // Extended ccmap operation (HasGlyphExt) can check the flag before it does
247 // extended ccmap specific operation. So HasGlyphExt can be applied to basic ccmap
253 #define CCMAP_BITS_PER_PAGE_LOG2 8
254 #define CCMAP_BITS_PER_PAGE CCMAP_POW2(CCMAP_BITS_PER_PAGE_LOG2)
255 #define CCMAP_BIT_INDEX(c) ((c) & PR_BITMASK(CCMAP_BITS_PER_ALU_LOG2))
256 #define CCMAP_ALU_INDEX(c) (((c)>>CCMAP_BITS_PER_ALU_LOG2) \
257 & PR_BITMASK(CCMAP_BITS_PER_PAGE_LOG2 - CCMAP_BITS_PER_ALU_LOG2))
259 #define CCMAP_PAGE_MASK PR_BITMASK(CCMAP_BITS_PER_PAGE_LOG2)
260 #define CCMAP_NUM_PRUINT16S_PER_PAGE \
261 (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_PRUINT16)
263 #define CCMAP_NUM_ALUS_PER_PAGE (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_ALU)
264 #define CCMAP_NUM_UCHARS_PER_PAGE CCMAP_BITS_PER_PAGE
269 #define CCMAP_BITS_PER_MID_LOG2 4
270 #define CCMAP_MID_INDEX(c) \
271 (((c)>>CCMAP_BITS_PER_PAGE_LOG2) & PR_BITMASK(CCMAP_BITS_PER_MID_LOG2))
272 #define CCMAP_NUM_MID_POINTERS CCMAP_POW2(CCMAP_BITS_PER_MID_LOG2)
273 #define CCMAP_NUM_UCHARS_PER_MID \
274 CCMAP_POW2(CCMAP_BITS_PER_MID_LOG2+CCMAP_BITS_PER_PAGE_LOG2)
279 #define CCMAP_BITS_PER_UPPER_LOG2 4
280 #define CCMAP_UPPER_INDEX(c) \
281 (((c)>>(CCMAP_BITS_PER_MID_LOG2+CCMAP_BITS_PER_PAGE_LOG2)) \
282 & PR_BITMASK(CCMAP_BITS_PER_UPPER_LOG2))
283 #define CCMAP_NUM_UPPER_POINTERS CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2)
288 #define CCMAP_BITS_PER_PRUINT16_LOG2 4
289 #define CCMAP_BITS_PER_PRUINT32_LOG2 5
291 #define CCMAP_BITS_PER_PRUINT16 CCMAP_POW2(CCMAP_BITS_PER_PRUINT16_LOG2)
292 #define CCMAP_BITS_PER_PRUINT32 CCMAP_POW2(CCMAP_BITS_PER_PRUINT32_LOG2)
293 #define CCMAP_BITS_PER_ALU CCMAP_POW2(CCMAP_BITS_PER_ALU_LOG2)
295 #define CCMAP_ALUS_PER_PRUINT32 (CCMAP_BITS_PER_PRUINT32/CCMAP_BITS_PER_ALU)
296 #define CCMAP_PRUINT32S_PER_ALU (CCMAP_BITS_PER_ALU/CCMAP_BITS_PER_PRUINT32)
297 #define CCMAP_PRUINT32S_PER_PAGE (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_PRUINT32)
299 #define CCMAP_ALU_MASK PR_BITMASK(CCMAP_BITS_PER_ALU_LOG2)
300 #define CCMAP_ALUS_PER_PAGE CCMAP_POW2(CCMAP_BITS_PER_PAGE_LOG2 \
301 - CCMAP_BITS_PER_ALU_LOG2)
302 #define NUM_UNICODE_CHARS CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2 \
303 +CCMAP_BITS_PER_MID_LOG2 \
304 +CCMAP_BITS_PER_PAGE_LOG2)
305 #define CCMAP_TOTAL_PAGES CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2 \
306 +CCMAP_BITS_PER_MID_LOG2)
308 #define CCMAP_BEGIN_AT_START_OF_MAP 0xFFFFFFFF
311 // Finally, build up the macro to test the bit for a given char
314 // offset from base to mid array
315 #define CCMAP_TO_MID(m,c) ((m)[CCMAP_UPPER_INDEX(c)])
317 // offset from base to page
318 #define CCMAP_TO_PAGE(m,c) ((m)[CCMAP_TO_MID((m),(c)) + CCMAP_MID_INDEX(c)])
320 // offset from base to alu
321 #define CCMAP_TO_ALU(m,c) \
322 (*((ALU_TYPE*)(&((m)[CCMAP_TO_PAGE((m),(c))])) + CCMAP_ALU_INDEX(c)))
325 #define CCMAP_HAS_CHAR(m,c) (((CCMAP_TO_ALU(m,c))>>CCMAP_BIT_INDEX(c)) & 1)
328 #define CCMAP_UNSET_CHAR(m,c) (CCMAP_TO_ALU(m,c) &= ~(CCMAP_POW2(CCMAP_BIT_INDEX(c))))
330 #define CCMAP_SIZE(m) (*((m)-1))
331 #define CCMAP_FLAG(m) (*((m)-2))
332 #define CCMAP_EXTRA (sizeof(ALU_TYPE)/sizeof(PRUint16)>2? sizeof(ALU_TYPE)/sizeof(PRUint16): 2)
333 #define CCMAP_SURROGATE_FLAG 0x0001
334 #define CCMAP_NONE_FLAG 0x0000
336 // get plane number from ccmap, bmp excluded, so plane 1's number is 0.
337 #define CCMAP_PLANE_FROM_SURROGATE(h) ((((PRUint16)(h) - (PRUint16)0xd800) >> 6) + 1)
339 // same as above, but get plane number from a ucs4 char
340 #define CCMAP_PLANE(u) ((((PRUint32)(u))>>16))
342 // scalar value inside the plane
343 #define CCMAP_INPLANE_OFFSET(h, l) (((((PRUint16)(h) - (PRUint16)0xd800) & 0x3f) << 10) + ((PRUint16)(l) - (PRUint16)0xdc00))
345 // get ccmap for that plane
346 #define CCMAP_FOR_PLANE_EXT(m, i) ((m) + ((PRUint32*)((m) + CCMAP_SIZE(m)))[(i)-1])
348 // test the bit for surrogate pair
349 #define CCMAP_HAS_CHAR_EXT2(m, h, l) (CCMAP_FLAG(m) & CCMAP_SURROGATE_FLAG && \
350 CCMAP_HAS_CHAR(CCMAP_FOR_PLANE_EXT((m), CCMAP_PLANE_FROM_SURROGATE(h)), CCMAP_INPLANE_OFFSET(h, l)))
351 // test the bit for a character in UCS4
352 #define CCMAP_HAS_CHAR_EXT(m, ucs4) (((ucs4)&0xffff0000) ? \
353 (CCMAP_FLAG(m) & CCMAP_SURROGATE_FLAG) && CCMAP_HAS_CHAR(CCMAP_FOR_PLANE_EXT((m), CCMAP_PLANE(ucs4)), (ucs4) & 0xffff) : \
354 CCMAP_HAS_CHAR(m, (PRUnichar)(ucs4)) )
356 // macros to ensure that the array defining a pre-compiled CCMap starts
357 // at an ALU_TYPE boundary instead of just a PRUint16 boundary.
358 // When invoking the macro, 'typequal' should be either 'const'
359 // or empty (NULL). see bug 224337.
361 #define DEFINE_ANY_CCMAP(var, extra, typequal) \
362 static typequal union { \
363 PRUint16 array[var ## _SIZE]; \
367 { var ## _INITIALIZER } \
369 static typequal PRUint16* var = var ## Union.array + extra
371 #define DEFINE_CCMAP(var, typequal) DEFINE_ANY_CCMAP(var, 0, typequal)
372 #define DEFINE_X_CCMAP(var, typequal) DEFINE_ANY_CCMAP(var, CCMAP_EXTRA, typequal)
374 #endif // NSCOMPRESSEDCHARMAP_H