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 return StringWidth(inBuffer.Text(), fromOffset, length, inStyle); 152 } 153 154 155 /*! \brief Searches for the table for the given font. 156 \param inStyle The font to search for. 157 \param outIndex a pointer to an int32, where the function will store 158 the index of the table, if found, or -1, if not. 159 \return \c true if the function founds the table, 160 \c false if not. 161 */ 162 bool 163 _BWidthBuffer_::FindTable(const BFont *inStyle, int32 *outIndex) 164 { 165 if (inStyle == NULL) 166 return false; 167 168 float fontSize = inStyle->Size(); 169 int32 fontCode = inStyle->FamilyAndStyle(); 170 int32 tableIndex = -1; 171 172 for (int32 i = 0; i < fItemCount; i++) { 173 174 #if USE_DANO_WIDTHBUFFER 175 if (*inStyle == fBuffer[i].font) 176 #else 177 if (fontSize == fBuffer[i].fontSize 178 && fontCode == fBuffer[i].fontCode) 179 #endif 180 { 181 tableIndex = i; 182 break; 183 } 184 } 185 if (outIndex != NULL) 186 *outIndex = tableIndex; 187 188 return tableIndex != -1; 189 } 190 191 192 /*! \brief Creates and insert an empty table for the given font. 193 \param font The font to create the table for. 194 \return The index of the newly created table. 195 */ 196 int32 197 _BWidthBuffer_::InsertTable(const BFont *font) 198 { 199 _width_table_ table; 200 hashed_escapement *deltas = new hashed_escapement[kTableCount]; 201 202 #if USE_DANO_WIDTHBUFFER 203 table.font = *font; 204 #else 205 table.fontSize = font->Size(); 206 table.fontCode = font->FamilyAndStyle(); 207 #endif 208 209 table.hashCount = 0; 210 table.tableCount = kTableCount; 211 table.widths = deltas; 212 213 uint32 position = fItemCount; 214 InsertItemsAt(1, position, &table); 215 216 return position; 217 } 218 219 /*! \brief Gets the escapement for the given charachter. 220 \param value An integer which uniquely identifies a charachter. 221 \param index The index of the table to search. 222 \param escapement A pointer to a float, where the function will 223 store the escapement. 224 \return \c true if the function could find the escapement 225 for the given charachter, \c false if not. 226 */ 227 bool 228 _BWidthBuffer_::GetEscapement(uint32 value, int32 index, float *escapement) 229 { 230 const _width_table_ &table = fBuffer[index]; 231 const hashed_escapement *widths = static_cast<hashed_escapement *>(table.widths); 232 uint32 hashed = Hash(value) & (table.tableCount - 1); 233 234 DEBUG_ONLY(uint32 iterations = 1;) 235 uint32 found; 236 while ((found = widths[hashed].code) != kInvalidCode) { 237 if (found == value) 238 break; 239 240 if (++hashed >= (uint32)table.tableCount) 241 hashed = 0; 242 DEBUG_ONLY(iterations++;) 243 } 244 245 if (found == kInvalidCode) 246 return false; 247 248 //PRINT(("Value found with %d iterations\n", iterations)); 249 250 if (escapement != NULL) 251 *escapement = widths[hashed].escapement; 252 253 return true; 254 } 255 256 257 uint32 258 _BWidthBuffer_::Hash(uint32 val) 259 { 260 uint32 shifted = val >> 24; 261 uint32 result = (val >> 15) + (shifted * 3); 262 263 result ^= (val >> 6) - (shifted * 22); 264 result ^= (val << 3); 265 266 return result; 267 } 268 269 270 /*! \brief Gets the escapements for the given string, and put them into 271 the hash table. 272 \param inText The string to be examined. 273 \param numChars The amount of charachters contained in the string. 274 \param textLen the amount of bytes contained in the string. 275 \param tableIndex the index of the table where the escapements 276 should be put. 277 \param inStyle the font. 278 \return The width of the supplied string (which should be multiplied by 279 the size of the font). 280 */ 281 float 282 _BWidthBuffer_::HashEscapements(const char *inText, int32 numChars, int32 textLen, 283 int32 tableIndex, const BFont *inStyle) 284 { 285 float *escapements = new float[numChars]; 286 inStyle->GetEscapements(inText, numChars, escapements); 287 288 _width_table_ &table = fBuffer[tableIndex]; 289 hashed_escapement *widths = static_cast<hashed_escapement *>(table.widths); 290 291 int32 offset = 0; 292 int32 charCount = 0; 293 294 // Insert the escapements into the hash table 295 do { 296 const int32 charLen = UTF8NextCharLen(inText + offset); 297 if (charLen == 0) 298 break; 299 300 const uint32 value = CharToCode(inText + offset, charLen); 301 302 uint32 hashed = Hash(value) & (table.tableCount - 1); 303 uint32 found = widths[hashed].code; 304 305 // Check if the value is already in the table 306 if (found != value) { 307 while ((found = widths[hashed].code) != kInvalidCode) { 308 if (found == value) 309 break; 310 if (++hashed >= (uint32)table.tableCount) 311 hashed = 0; 312 } 313 314 if (found == kInvalidCode) { 315 // The value is not in the table. Add it. 316 widths[hashed].code = value; 317 widths[hashed].escapement = escapements[charCount]; 318 table.hashCount++; 319 320 // We always keep some free space in the hash table 321 // TODO: Not sure how much space, currently we double 322 // the current size when hashCount is at least 2/3 of 323 // the total size. 324 if (table.tableCount * 2 / 3 <= table.hashCount) { 325 table.hashCount = 0; 326 const int32 newSize = table.tableCount * 2; 327 328 // Create and initialize a new hash table 329 hashed_escapement *newWidths = new hashed_escapement[newSize]; 330 331 // Rehash the values, and put them into the new table 332 for (int32 oldPos = 0; oldPos < table.tableCount; oldPos++) { 333 if (widths[oldPos].code != kInvalidCode) { 334 uint32 newPos = Hash(widths[oldPos].code) & (newSize - 1); 335 while (newWidths[newPos].code != kInvalidCode) { 336 if (++newPos >= (uint32)newSize) 337 newPos = 0; 338 } 339 newWidths[newPos].code = widths[oldPos].code; 340 newWidths[newPos].escapement = widths[oldPos].escapement; 341 table.hashCount++; 342 } 343 } 344 table.tableCount = newSize; 345 346 // Delete the old table, and put the new pointer into the _width_table_ 347 delete[] widths; 348 widths = newWidths; 349 } 350 } 351 } 352 charCount++; 353 offset += charLen; 354 } while (offset < textLen); 355 356 // Calculate the width of the string 357 float width = 0; 358 for (int32 x = 0; x < numChars; x++) 359 width += escapements[x]; 360 361 delete[] escapements; 362 363 return width; 364 } 365