Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2000-09-28
2001-10-16
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C382S232000
Reexamination Certificate
active
06304198
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the storage of bitmap font data within data processing systems.
2. Description of the Prior Art
Within data processing systems text data is typically stored as a sequence of character codes. When it is desired to present the text data to a user, for example by displaying it on a screen or printing it, then it is necessary to convert each character code into a graphical form that can be presented to a user. This conversion uses font data that specifies a graphical form for each character code. One type of font data is that in which a bitmap representation of the character is stored for each character code. Such bitmaps can be relatively simply processed for display or printing.
A problem that arises in such systems is the amount of storage capacity utilised in storing the font data and any associated data for accessing that font data. The amount of memory resource consumed can be a particular problem in the case of pictograph characters (such as Chinese, Korean and Japanese characters) where the number of characters that need to be represented can be very high, e.g. a Chinese pictograph font may include 13,000 different pictograph characters.
Measures that can reduce the amount of storage capacity needed to deal with font data are strongly desirable.
SUMMARY OF THE INVENTION
Viewed from one aspect the present invention provides apparatus for mapping an A-bit code to a storage location within a memory of variable length code data representing said A-bit code, said apparatus comprising:
(i) first lookup logic responsive to a B-bit field within said A-bit code for accessing a first lookup table entry corresponding to said B-bit field within in a first lookup table, said first lookup table entry including a second lookup table offset value pointing to a region within a second lookup table containing a plurality of second lookup table entries, a variable length code offset value and an average size value;
(ii) second lookup logic responsive to a C-bit field within said A-bit code for accessing a second lookup table entry corresponding to said C-bit field within said region of said second lookup table indicated by said second lookup table offset value, said second lookup table entry including an error value;
(iii) storage location calculating logic for calculating an address within said memory of said storage location from:
(iv) said variable length code offset value;
(v) a function of said average size value and a location within said region of said second lookup table that matched said C-bit field; and
(vi) said error value; and
(vii) storage accessing logic for reading said variable length data from said address within said memory.
This aspect of the invention seeks to reduce the overhead associated with accessing data in the form of variable length code data representing, for example, pixel bitmaps of a character. Whilst variable length coding of pixel bitmaps can produce a high degree of compression, it raises the difficulty of how to identify which particular portion of such variable length coded data represents a given character. The invention provides an improved mechanism for identifying such a portion of variable length coded data using a first lookup table and a second lookup table in a manner that advantageously reduces the amount of storage capacity required by the tables. In particular, the invention exploits the realisation that the position of the variable length coded data corresponding to a particular character can be estimated with only the error in that estimation having to be stored for an individual character thereby reducing the overall storage capacity needed for such lookup operations.
In preferred embodiments of the invention said region of said second lookup table contains a sequence of second lookup table entries sorted according to said A-bit code value such that with said region of said second lookup table said second entries are sorted in accordance with said C-bit field.
Sorting the regions of the second lookup table in accordance with the A-bit code value gives a predictability to the way that the data is arranged within the second lookup table that can be exploited to make it more efficient to identify the particular entry within the second lookup table when searching through the region concerned.
A particularly convenient way of encoding extra information into the second table is to use the position of the entry matching the character being sought within the region of the second table as an indicator of where the corresponding variable length coded data will lie within the font data as a whole. More particularly, if the entry in the second table is the Nth entry in the region and the average size of the variable length coded data for a font character is known from the first table, then multiplying these two values can give an additional offset into the variable length coded data as a whole making the approximation to the location more accurate.
A preferred way of interpreting the character code to access the first table and the second table is to use the B most significant bits of the code to index the first table and then use the C least significant bits of the code to search for a matching entry within the region of the second table pointed to by the entry indexed within the first table.
The techniques of the present invention may be usefully employed for many different types of font, but are particularly usefull when the font is a pictograph font. Pictograph fonts typically include a high number of different characters and so the data storage requirements are a more critical concern. In addition, there are typically many gaps m the character code sequence making table lookups more difficult.
The font data may be stored in different ways. For example, the font data could be stored on non-volatile magnetic storage media, such as a computer hard disk. However, the invention is particularly suited to systems in which the font data is stored in integrated circuit memory as such integrated circuit memory is typically relatively expensive to provide and so measures that reduce the amount needed are highly advantageous.
Whilst it will be appreciated that special purpose logic circuits may be provided to perform the various functions needed to carry out the technique of the invention, in many cases the best way to embody the technique will be to use data processing logic operating under software control whereby the software configures the data processing logic to act as the various different logic elements referred to above.
Viewed from a complementary aspect the present invention provides apparatus generating mapping data for mapping an A-bit code to a storage location within a memory of variable length code data representing said A-bit code, said apparatus comprising:
(i) first lookup table generating logic for generating a first lookup table such that a B-bit field within said A-bit code indicates a first lookup table entry corresponding to said B-bit field within in a first lookup table, said first lookup table entry including a second lookup table offset value pointing to a region within a second lookup table containing a plurality of second lookup table entries, a variable length code offset value and an average size value; and
(ii) second lookup table generating logic for generating a second lookup table such that a C-bit field within said A-bit code indicates a second lookup table entry corresponding to said C-bit field within said region of said second lookup table indicated by said second lookup table offset value, said second lookup table entry including an error value; wherein
(iii) an address within said memory of said storage location may be calculated from:
(iv) said variable length code offset value;
(v) a function of said average size value and a location within said region
(vi) of said second lookup table that matched said C-bit field; and said error value.
Viewed from another aspect the invention provides a method of mapping an A-bit code to a storage locat
ARM Limited
Jean-Pierre Peguy
Nixon & Vanderhye P.C.
LandOfFree
Bitmap font data storage within data processing systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bitmap font data storage within data processing systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bitmap font data storage within data processing systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604989