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