hb-private.hh revision 6843569d2c70c1771ce964e3d1a4cf91e14e7687
1/* 2 * Copyright © 2007,2008,2009 Red Hat, Inc. 3 * Copyright © 2011 Google, Inc. 4 * 5 * This is part of HarfBuzz, a text shaping library. 6 * 7 * Permission is hereby granted, without written agreement and without 8 * license or royalty fees, to use, copy, modify, and distribute this 9 * software and its documentation for any purpose, provided that the 10 * above copyright notice and the following two paragraphs appear in 11 * all copies of this software. 12 * 13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 17 * DAMAGE. 18 * 19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 21 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 24 * 25 * Red Hat Author(s): Behdad Esfahbod 26 * Google Author(s): Behdad Esfahbod 27 */ 28 29#ifndef HB_PRIVATE_HH 30#define HB_PRIVATE_HH 31 32#if HAVE_CONFIG_H 33#include "config.h" 34#endif 35 36#include "hb-common.h" 37 38#include <stdlib.h> 39#include <string.h> 40#include <assert.h> 41 42/* We only use these two for debug output. However, the debug code is 43 * always seen by the compiler (and optimized out in non-debug builds. 44 * If including these becomes a problem, we can start thinking about 45 * someway around that. */ 46#include <stdio.h> 47#include <errno.h> 48 49HB_BEGIN_DECLS 50 51 52/* Essentials */ 53 54#ifndef NULL 55# define NULL ((void *) 0) 56#endif 57 58#undef FALSE 59#define FALSE 0 60 61#undef TRUE 62#define TRUE 1 63 64 65/* Basics */ 66 67HB_END_DECLS 68 69#undef MIN 70template <typename Type> static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; } 71 72#undef MAX 73template <typename Type> static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; } 74 75HB_BEGIN_DECLS 76 77#undef ARRAY_LENGTH 78#define ARRAY_LENGTH(__array) ((signed int) (sizeof (__array) / sizeof (__array[0]))) 79 80#define HB_STMT_START do 81#define HB_STMT_END while (0) 82 83#define _ASSERT_STATIC1(_line, _cond) typedef int _static_assert_on_line_##_line##_failed[(_cond)?1:-1] 84#define _ASSERT_STATIC0(_line, _cond) _ASSERT_STATIC1 (_line, (_cond)) 85#define ASSERT_STATIC(_cond) _ASSERT_STATIC0 (__LINE__, (_cond)) 86 87#define ASSERT_STATIC_EXPR(_cond) ((void) sizeof (char[(_cond) ? 1 : -1])) 88 89 90/* Lets assert int types. Saves trouble down the road. */ 91 92ASSERT_STATIC (sizeof (int8_t) == 1); 93ASSERT_STATIC (sizeof (uint8_t) == 1); 94ASSERT_STATIC (sizeof (int16_t) == 2); 95ASSERT_STATIC (sizeof (uint16_t) == 2); 96ASSERT_STATIC (sizeof (int32_t) == 4); 97ASSERT_STATIC (sizeof (uint32_t) == 4); 98ASSERT_STATIC (sizeof (int64_t) == 8); 99ASSERT_STATIC (sizeof (uint64_t) == 8); 100 101ASSERT_STATIC (sizeof (hb_codepoint_t) == 4); 102ASSERT_STATIC (sizeof (hb_position_t) == 4); 103ASSERT_STATIC (sizeof (hb_mask_t) == 4); 104ASSERT_STATIC (sizeof (hb_var_int_t) == 4); 105 106/* Misc */ 107 108 109#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) 110#define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0) 111#define likely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 1)) 112#define unlikely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 0)) 113#else 114#define likely(expr) (expr) 115#define unlikely(expr) (expr) 116#endif 117 118#ifndef __GNUC__ 119#undef __attribute__ 120#define __attribute__(x) 121#endif 122 123#if __GNUC__ >= 3 124#define HB_PURE_FUNC __attribute__((pure)) 125#define HB_CONST_FUNC __attribute__((const)) 126#else 127#define HB_PURE_FUNC 128#define HB_CONST_FUNC 129#endif 130#if __GNUC__ >= 4 131#define HB_UNUSED __attribute__((unused)) 132#else 133#define HB_UNUSED 134#endif 135 136#ifndef HB_INTERNAL 137# define HB_INTERNAL __attribute__((__visibility__("hidden"))) 138#endif 139 140 141#if (defined(__WIN32__) && !defined(__WINE__)) || defined(_MSC_VER) 142#define snprintf _snprintf 143#endif 144 145#ifdef _MSC_VER 146#undef inline 147#define inline __inline 148#endif 149 150#ifdef __STRICT_ANSI__ 151#undef inline 152#define inline __inline__ 153#endif 154 155 156#if __GNUC__ >= 3 157#define HB_FUNC __PRETTY_FUNCTION__ 158#elif defined(_MSC_VER) 159#define HB_FUNC __FUNCSIG__ 160#else 161#define HB_FUNC __func__ 162#endif 163 164 165/* Return the number of 1 bits in mask. */ 166static inline HB_CONST_FUNC unsigned int 167_hb_popcount32 (uint32_t mask) 168{ 169#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) 170 return __builtin_popcount (mask); 171#else 172 /* "HACKMEM 169" */ 173 register uint32_t y; 174 y = (mask >> 1) &033333333333; 175 y = mask - y - ((y >>1) & 033333333333); 176 return (((y + (y >> 3)) & 030707070707) % 077); 177#endif 178} 179 180/* Returns the number of bits needed to store number */ 181static inline HB_CONST_FUNC unsigned int 182_hb_bit_storage (unsigned int number) 183{ 184#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 185 return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number)) : 0; 186#else 187 register unsigned int n_bits = 0; 188 while (number) { 189 n_bits++; 190 number >>= 1; 191 } 192 return n_bits; 193#endif 194} 195 196/* Returns the number of zero bits in the least significant side of number */ 197static inline HB_CONST_FUNC unsigned int 198_hb_ctz (unsigned int number) 199{ 200#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 201 return likely (number) ? __builtin_ctz (number) : 0; 202#else 203 register unsigned int n_bits = 0; 204 if (unlikely (!number)) return 0; 205 while (!(number & 1)) { 206 n_bits++; 207 number >>= 1; 208 } 209 return n_bits; 210#endif 211} 212 213static inline bool 214_hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size) 215{ 216 return (size > 0) && (count >= ((unsigned int) -1) / size); 217} 218 219 220/* Type of bsearch() / qsort() compare function */ 221typedef int (*hb_compare_func_t) (const void *, const void *); 222 223 224HB_END_DECLS 225 226 227/* arrays and maps */ 228 229 230template <typename Type, unsigned int StaticSize> 231struct hb_prealloced_array_t { 232 233 unsigned int len; 234 unsigned int allocated; 235 Type *array; 236 Type static_array[StaticSize]; 237 238 inline Type& operator [] (unsigned int i) 239 { 240 return array[i]; 241 } 242 243 inline Type *push (void) 244 { 245 if (!array) { 246 array = static_array; 247 allocated = ARRAY_LENGTH (static_array); 248 } 249 if (likely (len < allocated)) 250 return &array[len++]; 251 252 /* Need to reallocate */ 253 unsigned int new_allocated = allocated + (allocated >> 1) + 8; 254 Type *new_array = NULL; 255 256 if (array == static_array) { 257 new_array = (Type *) calloc (new_allocated, sizeof (Type)); 258 if (new_array) 259 memcpy (new_array, array, len * sizeof (Type)); 260 } else { 261 bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); 262 if (likely (!overflows)) { 263 new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); 264 } 265 } 266 267 if (unlikely (!new_array)) 268 return NULL; 269 270 array = new_array; 271 allocated = new_allocated; 272 return &array[len++]; 273 } 274 275 inline void pop (void) 276 { 277 len--; 278 /* TODO: shrink array if needed */ 279 } 280 281 inline void shrink (unsigned int l) 282 { 283 if (l < len) 284 len = l; 285 /* TODO: shrink array if needed */ 286 } 287 288 template <typename T> 289 inline Type *find (T v) { 290 for (unsigned int i = 0; i < len; i++) 291 if (array[i] == v) 292 return &array[i]; 293 return NULL; 294 } 295 template <typename T> 296 inline const Type *find (T v) const { 297 for (unsigned int i = 0; i < len; i++) 298 if (array[i] == v) 299 return &array[i]; 300 return NULL; 301 } 302 303 inline void sort (void) 304 { 305 qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 306 } 307 308 template <typename T> 309 inline Type *bsearch (T *key) 310 { 311 return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 312 } 313 template <typename T> 314 inline const Type *bsearch (T *key) const 315 { 316 return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 317 } 318}; 319 320template <typename Type> 321struct hb_array_t : hb_prealloced_array_t<Type, 2> {}; 322 323 324template <typename item_t> 325struct hb_set_t 326{ 327 hb_array_t <item_t> items; 328 329 public: 330 331 template <typename T> 332 inline bool insert (T v) 333 { 334 item_t *item = items.find (v); 335 if (item) 336 item->finish (); 337 else 338 item = items.push (); 339 if (unlikely (!item)) return false; 340 *item = v; 341 return true; 342 } 343 344 template <typename T> 345 inline void remove (T v) 346 { 347 item_t *item = items.find (v); 348 if (!item) return; 349 350 item->finish (); 351 *item = items[items.len - 1]; 352 items.pop (); 353 } 354 355 template <typename T> 356 inline item_t *get (T v) 357 { 358 return items.find (v); 359 } 360 361 void finish (void) { 362 for (unsigned i = 0; i < items.len; i++) 363 items[i].finish (); 364 } 365 366}; 367 368 369HB_BEGIN_DECLS 370 371 372/* Big-endian handling */ 373 374static inline uint16_t hb_be_uint16 (const uint16_t v) 375{ 376 const uint8_t *V = (const uint8_t *) &v; 377 return (uint16_t) (V[0] << 8) + V[1]; 378} 379 380#define hb_be_uint16_put(v,V) HB_STMT_START { v[0] = (V>>8); v[1] = (V); } HB_STMT_END 381#define hb_be_uint16_get(v) (uint16_t) ((v[0] << 8) + v[1]) 382#define hb_be_uint16_eq(a,b) (a[0] == b[0] && a[1] == b[1]) 383 384#define hb_be_uint32_put(v,V) HB_STMT_START { v[0] = (V>>24); v[1] = (V>>16); v[2] = (V>>8); v[3] = (V); } HB_STMT_END 385#define hb_be_uint32_get(v) (uint32_t) ((v[0] << 24) + (v[1] << 16) + (v[2] << 8) + v[3]) 386#define hb_be_uint32_eq(a,b) (a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]) 387 388 389/* ASCII tag/character handling */ 390 391static inline unsigned char ISALPHA (unsigned char c) 392{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } 393static inline unsigned char ISALNUM (unsigned char c) 394{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } 395static inline unsigned char TOUPPER (unsigned char c) 396{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; } 397static inline unsigned char TOLOWER (unsigned char c) 398{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; } 399 400#define HB_TAG_CHAR4(s) (HB_TAG(((const char *) s)[0], \ 401 ((const char *) s)[1], \ 402 ((const char *) s)[2], \ 403 ((const char *) s)[3])) 404 405 406/* Debug */ 407 408#ifndef HB_DEBUG 409#define HB_DEBUG 0 410#endif 411 412static inline bool /* always returns TRUE */ 413_hb_trace (const char *what, 414 const char *function, 415 const void *obj, 416 unsigned int depth, 417 unsigned int max_depth) 418{ 419 (void) ((depth < max_depth) && fprintf (stderr, "%s(%p) %-*d-> %s\n", what, obj, depth, depth, function)); 420 return TRUE; 421} 422 423 424HB_END_DECLS 425 426#endif /* HB_PRIVATE_HH */ 427