Added SearchUShort and SearchULong.
git-svn-id: http://sfntly.googlecode.com/svn/trunk/cpp/src@57 672e30a5-4c29-85ac-ac6d-611c735e0a51
diff --git a/sfntly/data/readable_font_data.cc b/sfntly/data/readable_font_data.cc
index 8f43575..6ceb38c 100644
--- a/sfntly/data/readable_font_data.cc
+++ b/sfntly/data/readable_font_data.cc
@@ -16,6 +16,9 @@
#include "sfntly/data/memory_byte_array.h"
#include "sfntly/data/readable_font_data.h"
+
+#include <stdio.h>
+
#include "sfntly/data/writable_font_data.h"
#include "sfntly/port/exception_type.h"
@@ -156,6 +159,71 @@
return array_->CopyTo(ba, BoundOffset(0), Length());
}
+int32_t ReadableFontData::SearchUShort(int32_t start_index,
+ int32_t start_offset,
+ int32_t end_index,
+ int32_t end_offset,
+ int32_t length,
+ int32_t key) {
+ int32_t location = 0;
+ int32_t bottom = 0;
+ int32_t top = length;
+ while (top != bottom) {
+ location = (top + bottom) / 2;
+ int32_t location_start = ReadUShort(start_index + location * start_offset);
+ if (key < location_start) {
+ // location is below current location
+ top = location;
+ } else {
+ // is key below the upper bound?
+ int32_t location_end = ReadUShort(end_index + location * end_offset);
+#if defined (SFNTLY_DEBUG_FONTDATA)
+ fprintf(stderr, "**start: %d; end: %d\n", location_start, location_end);
+#endif
+ if (key <= location_end) {
+ return location;
+ } else {
+ // location is above the current location
+ bottom = location + 1;
+ }
+ }
+ }
+ return -1;
+}
+
+int32_t ReadableFontData::SearchULong(int32_t start_index,
+ int32_t start_offset,
+ int32_t end_index,
+ int32_t end_offset,
+ int32_t length,
+ int32_t key) {
+ int32_t location = 0;
+ int32_t bottom = 0;
+ int32_t top = length;
+ while (top != bottom) {
+ location = (top + bottom) / 2;
+ int32_t location_start = ReadULongAsInt(start_index
+ + location * start_offset);
+ if (key < location_start) {
+ // location is below current location
+ top = location;
+ } else {
+ // is key below the upper bound?
+ int32_t location_end = ReadULongAsInt(end_index + location * end_offset);
+#if defined (SFNTLY_DEBUG_FONTDATA)
+ fprintf(stderr, "**start: %d; end: %d\n", location_start, location_end);
+#endif
+ if (key <= location_end) {
+ return location;
+ } else {
+ // location is above the current location
+ bottom = location + 1;
+ }
+ }
+ }
+ return -1;
+}
+
CALLER_ATTACH FontData* ReadableFontData::Slice(int32_t offset,
int32_t length) {
if (offset < 0 || offset + length > Size()) {
diff --git a/sfntly/data/readable_font_data.h b/sfntly/data/readable_font_data.h
index e7b3170..48b3e77 100644
--- a/sfntly/data/readable_font_data.h
+++ b/sfntly/data/readable_font_data.h
@@ -180,15 +180,55 @@
// Make gcc -Woverloaded-virtual happy.
virtual int32_t CopyTo(ByteArray* ba);
- // TODO(dfilimon): Implementation of following in review, need to merge.
+ // Search for the key value in the range tables provided.
+ //
+ // The search looks through the start-end pairs looking for the key value. It
+ // is assumed that the start-end pairs are both represented by UShort values,
+ // ranges do not overlap, and are monotonically increasing.
+ //
+ // @param startIndex the position to read the first start value from
+ // @param startOffset the offset between subsequent start values
+ // @param endIndex the position to read the first end value from
+ // @param endOffset the offset between subsequent end values
+ // @param length the number of start-end pairs
+ // @param key the value to search for
+ // @return the index of the start-end pairs in which the key was found; -1
+ // otherwise
+ int32_t SearchUShort(int32_t start_index,
+ int32_t start_offset,
+ int32_t end_index,
+ int32_t end_offset,
+ int32_t length,
+ int32_t key);
+
+ // Search for the key value in the range tables provided.
+ //
+ // The search looks through the start-end pairs looking for the key value. It
+ // is assumed that the start-end pairs are both represented by ULong values
+ // that can be represented within 31 bits, ranges do not overlap, and are
+ // monotonically increasing.
+ //
+ // @param startIndex the position to read the first start value from
+ // @param startOffset the offset between subsequent start values
+ // @param endIndex the position to read the first end value from
+ // @param endOffset the offset between subsequent end values
+ // @param length the number of start-end pairs
+ // @param key the value to search for
+ // @return the index of the start-end pairs in which the key was found; -1
+ // otherwise
+ int32_t SearchULong(int32_t start_index,
+ int32_t start_offset,
+ int32_t end_index,
+ int32_t end_offset,
+ int32_t length,
+ int32_t key);
+
+
+ // TODO(arthurhsu): IMPLEMENT
/*
- virtual int32_t SearchUShort(int32_t start, int32_t length, int32_t key);
- virtual int32_t SearchUShort(int32_t start_index, int32_t start_offset,
- int32_t count_index, int32_t count_offset,
- int32_t length, int32_t key);
- virtual int32_t SearchULong(int32_t start_index, int32_t start_offset,
- int32_t end_index, int32_t end_offset,
- int32_t length, int32_t key);
+ virtual int32_t ReadFUnit(int32_t index);
+ virtual int64_t ReadF2Dot14(int32_t index);
+ virtual int64_t ReadLongDateTime(int32_t index);
*/
// Makes a slice of this FontData. The returned slice will share the data with
diff --git a/test/font_data_test.cc b/test/font_data_test.cc
index 4de6fff..ecf9a62 100644
--- a/test/font_data_test.cc
+++ b/test/font_data_test.cc
@@ -25,7 +25,114 @@
namespace sfntly {
const int32_t BYTE_ARRAY_SIZES[] =
- {1, 7, 127, 128, 129, 255, 256, 257, 666, 1023, 0x10000};
+ {1, 7, 127, 128, 129, 255, 256, 257, 666, 1023, 0x10000};
+
+// array data for searching
+const int32_t LOWER_BYTE_ARRAY_FOR_SEARCHING[] = {2, 4, 7, 13, 127};
+const int32_t UPPER_BYTE_ARRAY_FOR_SEARCHING[] = {2, 5, 12, 16, 256};
+const int32_t kLowerByteArrayForSearchingLength = 5;
+const int32_t kUpperByteArrayForSearchingLength = 5;
+
+// search test result pairs - number to search for; index found at
+const int32_t SEARCH_TEST_PAIRS[][2] = {
+ {0, -1}, {1, -1}, {2, 0}, {3, -1}, {4, 1}, {5, 1}, {6, -1}, {12, 2},
+ {13, 3}, {17, -1}, {126, -1}, {127, 4}, {256, 4}, {257, -1}, {0x1000, -1}
+};
+const int32_t kSearchTestPairsLength = 15;
+
+// offset and start index data for searching data
+// array data size, lower_start_index, lower_offset, upper_start_index,
+// upper_offset
+const int32_t SEARCH_TEST_OFFSETS[][5] = {
+ // lower[], upper[]
+ { (kLowerByteArrayForSearchingLength + kUpperByteArrayForSearchingLength)
+ * sizeof(ushort),
+ 0,
+ sizeof(ushort),
+ kLowerByteArrayForSearchingLength * sizeof(ushort),
+ sizeof(ushort) },
+
+ // {lower, upper} []
+ { (kLowerByteArrayForSearchingLength + kUpperByteArrayForSearchingLength)
+ * sizeof(ushort),
+ 0,
+ 2 * sizeof(ushort),
+ sizeof(ushort),
+ 2 * sizeof(ushort) },
+
+ // upper[], lower[]
+ { (kLowerByteArrayForSearchingLength + kUpperByteArrayForSearchingLength)
+ * sizeof(ushort),
+ kLowerByteArrayForSearchingLength * sizeof(ushort),
+ sizeof(ushort),
+ 0,
+ sizeof(ushort) },
+
+ // {upper, lower} []
+ { (kLowerByteArrayForSearchingLength + kUpperByteArrayForSearchingLength)
+ * sizeof(ushort),
+ sizeof(ushort),
+ 2 * sizeof(ushort),
+ 0,
+ 2 * sizeof(ushort) }
+};
+const int32_t kSearchTestOffsetLength = 4;
+
+ReadableFontData*
+FillTestFontDataWithShortsForSearching(WritableFontData* wfd,
+ const int32_t* lower_data,
+ int32_t lower_start_index,
+ int32_t lower_offset,
+ const int32_t* upper_data,
+ int32_t upper_start_index,
+ int32_t upper_offset) {
+ // lower data
+ int offset = lower_start_index;
+ for (int32_t i = 0; i < kLowerByteArrayForSearchingLength; ++i) {
+ wfd->WriteUShort(offset, lower_data[i]);
+ offset += lower_offset;
+ }
+
+ // upper data
+ offset = upper_start_index;
+ for (int32_t i = 0; i < kUpperByteArrayForSearchingLength; ++i) {
+ wfd->WriteUShort(offset, upper_data[i]);
+ offset += upper_offset;
+ }
+
+ return wfd;
+}
+
+bool TestReadableFontDataSearching() {
+ for (int32_t i = 0; i < kSearchTestOffsetLength; ++i) {
+ const int32_t* array_setup_offset = SEARCH_TEST_OFFSETS[i];
+ WritableFontDataPtr wfd;
+ wfd.Attach(WritableFontData::CreateWritableFontData(array_setup_offset[0]));
+ FillTestFontDataWithShortsForSearching(wfd,
+ LOWER_BYTE_ARRAY_FOR_SEARCHING,
+ array_setup_offset[1],
+ array_setup_offset[2],
+ UPPER_BYTE_ARRAY_FOR_SEARCHING,
+ array_setup_offset[3],
+ array_setup_offset[4]);
+ for (int32_t j = 0; j < kSearchTestPairsLength; ++j) {
+ const int32_t* test_case = SEARCH_TEST_PAIRS[j];
+ int32_t found = wfd->SearchUShort(array_setup_offset[1],
+ array_setup_offset[2],
+ array_setup_offset[3],
+ array_setup_offset[4],
+ kLowerByteArrayForSearchingLength,
+ test_case[0]);
+#if defined (SFNTLY_DEBUG_FONTDATA)
+ fprintf(stderr, "Searching for %d; Got %d; Expected %d; "
+ "[test %d][offset %d]\n",
+ test_case[0], found, test_case[1], j, i);
+#endif
+ EXPECT_EQ(test_case[1], found);
+ }
+ }
+ return true;
+}
void FillTestByteArray(ByteArray* ba, int32_t size) {
for (int32_t i = 0; i < size; ++i) {
@@ -220,6 +327,10 @@
} // namespace sfntly
+TEST(FontData, ReadableFontDataSearching) {
+ ASSERT_TRUE(sfntly::TestReadableFontDataSearching());
+}
+
TEST(FontData, All) {
ASSERT_TRUE(sfntly::TestReadableFontData());
ASSERT_TRUE(sfntly::TestWritableFontData());
