1 /* 2 * Copyright 2003-2006, Haiku, Inc. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Stefano Ceccherini (burton666@libero.it) 7 */ 8 9 //! Caches string widths in a hash table, to avoid a trip to the app server. 10 11 12 #include "utf8_functions.h" 13 #include "TextGapBuffer.h" 14 #include "WidthBuffer.h" 15 16 #include <Debug.h> 17 #include <Font.h> 18 19 #include <stdio.h> 20 21 22 const static uint32 kTableCount = 128; 23 const static uint32 kInvalidCode = 0xFFFFFFFF; 24 25 26 struct hashed_escapement { 27 uint32 code; 28 float escapement; 29 30 hashed_escapement() 31 { 32 code = kInvalidCode; 33 escapement = 0; 34 } 35 }; 36 37 38 /*! \brief Convert a UTF8 char to a code, which will be used 39 to uniquely identify the charachter in the hash table. 40 \param text A pointer to the charachter to examine. 41 \param charLen the length of the charachter to examine. 42 \return The code for the given charachter, 43 */ 44 static inline uint32 45 CharToCode(const char *text, const int32 charLen) 46 { 47 uint32 value = 0; 48 int32 shiftVal = 24; 49 for (int32 c = 0; c < charLen; c++) { 50 value |= (text[c] << shiftVal); 51 shiftVal -= 8; 52 } 53 return value; 54 } 55 56 57 /*! \brief Initializes the object. 58 */ 59 _BWidthBuffer_::_BWidthBuffer_() 60 : 61 _BTextViewSupportBuffer_<_width_table_>(1, 0) 62 { 63 } 64 65 66 /*! \brief Frees the allocated resources. 67 */ 68 _BWidthBuffer_::~_BWidthBuffer_() 69 { 70 for (int32 x = 0; x < fItemCount; x++) 71 delete[] (hashed_escapement *)fBuffer[x].widths; 72 } 73 74 75 /*! \brief Returns how much room is required to draw a string in the font. 76 \param inText The string to be examined. 77 \param fromOffset The offset in the string where to begin the examination. 78 \param lenght The amount of bytes to be examined. 79 \param inStyle The font. 80 \return The space (in pixels) required to draw the given string. 81 */ 82 float 83 _BWidthBuffer_::StringWidth(const char *inText, int32 fromOffset, int32 length, 84 const BFont *inStyle) 85 { 86 if (inText == NULL) 87 return 0; 88 89 int32 index = 0; 90 if (!FindTable(inStyle, &index)) 91 index = InsertTable(inStyle); 92 93 char *text = NULL; 94 int32 numChars = 0; 95 int32 textLen = 0; 96 97 const float fontSize = inStyle->Size(); 98 float stringWidth = 0; 99 if (length > 0) { 100 for (int32 charLen = 0, currentOffset = fromOffset; 101 currentOffset < fromOffset + length; 102 currentOffset += charLen) { 103 charLen = UTF8NextCharLen(inText + currentOffset); 104 105 // End of string, bail out 106 if (charLen == 0) 107 break; 108 109 // Some magic, to uniquely identify this charachter 110 const uint32 value = CharToCode(inText + currentOffset, charLen); 111 112 float escapement; 113 if (GetEscapement(value, index, &escapement)) { 114 // Well, we've got a match for this charachter 115 stringWidth += escapement; 116 } else { 117 // Store this charachter into an array, which we'll 118 // pass to HashEscapements() later 119 int32 offset = textLen; 120 textLen += charLen; 121 numChars++; 122 text = (char *)realloc(text, textLen); 123 for (int32 x = 0; x < charLen; x++) 124 text[offset + x] = inText[currentOffset + x]; 125 } 126 } 127 } 128 129 if (text != NULL) { 130 // We've found some charachters which aren't yet in the hash table. 131 // Get their width via HashEscapements() 132 stringWidth += HashEscapements(text, numChars, textLen, index, inStyle); 133 free(text); 134 } 135 136 return stringWidth * fontSize; 137 } 138 139 140 /*! \brief Returns how much room is required to draw a string in the font. 141 \param inBuffer The _BTextGapBuffer_ to be examined. 142 \param fromOffset The offset in the _BTextGapBuffer_ where to begin the examination. 143 \param lenght The amount of bytes to be examined. 144 \param inStyle The font. 145 \return The space (in pixels) required to draw the given string. 146 */ 147 float 148 _BWidthBuffer_::StringWidth(_BTextGapBuffer_ &inBuffer, int32 fromOffset, int32 length, 149 const BFont *inStyle) 150 { 151 const char* text = inBuffer.GetString(fromOffset, &length); 152 return StringWidth(text, 0, length, inStyle); 153 } 154 155 156 /*! \brief Searches for the table for the given font. 157 \param inStyle The font to search for. 158 \param outIndex a pointer to an int32, where the function will store 159 the index of the table, if found, or -1, if not. 160 \return \c true if the function founds the table, 161 \c false if not. 162 */ 163 bool 164 _BWidthBuffer_::FindTable(const BFont *inStyle, int32 *outIndex) 165 { 166 if (inStyle == NULL) 167 return false; 168 169 float fontSize = inStyle->Size(); 170 int32 fontCode = inStyle->FamilyAndStyle(); 171 int32 tableIndex = -1; 172 173 for (int32 i = 0; i < fItemCount; i++) { 174 175 #if USE_DANO_WIDTHBUFFER 176 if (*inStyle == fBuffer[i].font) 177 #else 178 if (fontSize == fBuffer[i].fontSize 179 && fontCode == fBuffer[i].fontCode) 180 #endif 181 { 182 tableIndex = i; 183 break; 184 } 185 } 186 if (outIndex != NULL) 187 *outIndex = tableIndex; 188 189 return tableIndex != -1; 190 } 191 192 193 /*! \brief Creates and insert an empty table for the given font. 194 \param font The font to create the table for. 195 \return The index of the newly created table. 196 */ 197 int32 198 _BWidthBuffer_::InsertTable(const BFont *font) 199 { 200 _width_table_ table; 201 hashed_escapement *deltas = new hashed_escapement[kTableCount]; 202 203 #if USE_DANO_WIDTHBUFFER 204 table.font = *font; 205 #else 206 table.fontSize = font->Size(); 207 table.fontCode = font->FamilyAndStyle(); 208 #endif 209 210 table.hashCount = 0; 211 table.tableCount = kTableCount; 212 table.widths = deltas; 213 214 uint32 position = fItemCount; 215 InsertItemsAt(1, position, &table); 216 217 return position; 218 } 219 220 /*! \brief Gets the escapement for the given charachter. 221 \param value An integer which uniquely identifies a charachter. 222 \param index The index of the table to search. 223 \param escapement A pointer to a float, where the function will 224 store the escapement. 225 \return \c true if the function could find the escapement 226 for the given charachter, \c false if not. 227 */ 228 bool 229 _BWidthBuffer_::GetEscapement(uint32 value, int32 index, float *escapement) 230 { 231 const _width_table_ &table = fBuffer[index]; 232 const hashed_escapement *widths = static_cast<hashed_escapement *>(table.widths); 233 uint32 hashed = Hash(value) & (table.tableCount - 1); 234 235 DEBUG_ONLY(uint32 iterations = 1;) 236 uint32 found; 237 while ((found = widths[hashed].code) != kInvalidCode) { 238 if (found == value) 239 break; 240 241 if (++hashed >= (uint32)table.tableCount) 242 hashed = 0; 243 DEBUG_ONLY(iterations++;) 244 } 245 246 if (found == kInvalidCode) 247 return false; 248 249 //PRINT(("Value found with %d iterations\n", iterations)); 250 251 if (escapement != NULL) 252 *escapement = widths[hashed].escapement; 253 254 return true; 255 } 256 257 258 uint32 259 _BWidthBuffer_::Hash(uint32 val) 260 { 261 uint32 shifted = val >> 24; 262 uint32 result = (val >> 15) + (shifted * 3); 263 264 result ^= (val >> 6) - (shifted * 22); 265 result ^= (val << 3); 266 267 return result; 268 } 269 270 271 /*! \brief Gets the escapements for the given string, and put them into 272 the hash table. 273 \param inText The string to be examined. 274 \param numChars The amount of charachters contained in the string. 275 \param textLen the amount of bytes contained in the string. 276 \param tableIndex the index of the table where the escapements 277 should be put. 278 \param inStyle the font. 279 \return The width of the supplied string (which should be multiplied by 280 the size of the font). 281 */ 282 float 283 _BWidthBuffer_::HashEscapements(const char *inText, int32 numChars, int32 textLen, 284 int32 tableIndex, const BFont *inStyle) 285 { 286 float *escapements = new float[numChars]; 287 inStyle->GetEscapements(inText, numChars, escapements); 288 289 _width_table_ &table = fBuffer[tableIndex]; 290 hashed_escapement *widths = static_cast<hashed_escapement *>(table.widths); 291 292 int32 offset = 0; 293 int32 charCount = 0; 294 295 // Insert the escapements into the hash table 296 do { 297 const int32 charLen = UTF8NextCharLen(inText + offset); 298 if (charLen == 0) 299 break; 300 301 const uint32 value = CharToCode(inText + offset, charLen); 302 303 uint32 hashed = Hash(value) & (table.tableCount - 1); 304 uint32 found = widths[hashed].code; 305 306 // Check if the value is already in the table 307 if (found != value) { 308 while ((found = widths[hashed].code) != kInvalidCode) { 309 if (found == value) 310 break; 311 if (++hashed >= (uint32)table.tableCount) 312 hashed = 0; 313 } 314 315 if (found == kInvalidCode) { 316 // The value is not in the table. Add it. 317 widths[hashed].code = value; 318 widths[hashed].escapement = escapements[charCount]; 319 table.hashCount++; 320 321 // We always keep some free space in the hash table 322 // TODO: Not sure how much space, currently we double 323 // the current size when hashCount is at least 2/3 of 324 // the total size. 325 if (table.tableCount * 2 / 3 <= table.hashCount) { 326 table.hashCount = 0; 327 const int32 newSize = table.tableCount * 2; 328 329 // Create and initialize a new hash table 330 hashed_escapement *newWidths = new hashed_escapement[newSize]; 331 332 // Rehash the values, and put them into the new table 333 for (int32 oldPos = 0; oldPos < table.tableCount; oldPos++) { 334 if (widths[oldPos].code != kInvalidCode) { 335 uint32 newPos = Hash(widths[oldPos].code) & (newSize - 1); 336 while (newWidths[newPos].code != kInvalidCode) { 337 if (++newPos >= (uint32)newSize) 338 newPos = 0; 339 } 340 newWidths[newPos].code = widths[oldPos].code; 341 newWidths[newPos].escapement = widths[oldPos].escapement; 342 table.hashCount++; 343 } 344 } 345 table.tableCount = newSize; 346 347 // Delete the old table, and put the new pointer into the _width_table_ 348 delete[] widths; 349 widths = newWidths; 350 } 351 } 352 } 353 charCount++; 354 offset += charLen; 355 } while (offset < textLen); 356 357 // Calculate the width of the string 358 float width = 0; 359 for (int32 x = 0; x < numChars; x++) 360 width += escapements[x]; 361 362 delete[] escapements; 363 364 return width; 365 } 366