US5870084A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for efficiently storing and quickly retrieving glyphs for large character set languages in a set top box
Assignee: OpenTV Inc
•
Filing: 1996-11-12
•
Granted: 1999-02-09
•
Expires: 2016-11-12
Abstract
Abstract A system and method for receiving and rendering Unicode text in multiple languages on a set top box is disclosed. The system includes a set top box which receives an application program from a broadcast station. The set top box executes the application program. The application program includes Unicode character encoding text for display on a television coupled to the set top box. An operating environment running on the set top box includes a Unicode encoding engine which the application program invokes to display Unicode text. The encoding engine determines the language of characters in the text and invokes a rendering engine corresponding to the language of each character, thus enabling characters from different languages to be mixed in the same text string. The rendering engine has specific knowledge of the language, such as rendering direction and context. One or more glyph sets may be plugged in to the set top box to support different languages and fonts according the locale in which the set top box will be used. The rendering engine renders the characters using the glyphs in the glyph sets. Furthermore, glyphs not present in the set top box may be downloaded to the set top box along with the application program and rendered by a rendering engine. A set top box and method for efficiently storing and quickly retrieving the large number of Japanese Unicode characters using a hash table and hashing method in the set top box is also disclosed.
Inventors
- 👤 Rajesh Kanungo
- 👤 Richard K. Motofuji
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 05:08
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/40; H04N21/47; H04N21/488; H04N21/4884
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
175 words
A method for efficiently storing a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, the method comprising: receiving a character of said subset of characters, wherein said character comprises an encoding value and a glyph describing a graphic representation of said character; allocating storage for a hash bin comprising storage for an encoding value and a glyph; storing said encoding value and said glyph in said hash bin; calculating an index according to an equation index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index; adding said hash bin to said hash bin list; performing said receiving, said allocating, said storing, said calculating an index, said calculating a reference, and said adding for each character in said subset of characters.
Claim 2
Independent Claim
175 words
A method for efficiently storing a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, the method comprising: receiving a character of said subset of characters, wherein said character comprises an encoding value and a glyph describing a graphic representation of said character; allocating storage for a hash bin comprising storage for an encoding value and a glyph; storing said encoding value and said glyph in said hash bin; calculating an index according to an equation index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index; adding said hash bin to said hash bin list; performing said receiving, said allocating, said storing, said calculating an index, said calculating a reference, and said adding for each character in said subset of characters.
Claim 3
Dependent Claim
20 words
The method as recited in claim 1, wherein said set of encoding values comprises the Unicode set of encoding values.
Claim 4
Dependent Claim
19 words
The method as recited in claim 1, wherein said subset of characters comprises characters from at least one language.
Claim 5
Dependent Claim
30 words
The method as recited in claim 3, wherein said at least one language includes at least one from the group comprising: Japanese, Chinese, Korean, Thai, Arabic, Indic, and European languages.
Claim 6
Dependent Claim
24 words
The method as recited in claim 1, wherein said MASK1 constant is 0×0ff, said MASK2 constant is 0×07ff, and said SHIFTVAL constant is 8.
Claim 7
Dependent Claim
20 words
The method as recited in claim 1, wherein said hash table of references comprises 2048 references to hash bin lists.
Claim 8
Dependent Claim
42 words
The method as recited in claim 1, wherein said hash bin further comprises a reference to said glyph, wherein said storage for said bin comprises a first portion for said glyph and a second portion for said encoding value and said reference.
Claim 9
Dependent Claim
19 words
The method as recited in claim 1, wherein said hash bin list comprises a linked list of hash bins.
Claim 10
Dependent Claim
18 words
The method as recited in claim 1, wherein said hash bin list comprises an array of hash bins.
Claim 11
Dependent Claim
26 words
The method as recited in claim 8, wherein said reference to said hash bin list comprises a count of hash bins in said hash bin list.
Claim 12
Dependent Claim
24 words
The method as recited in claim 1, further comprising allocating storage for said hash table prior to said allocating storage for a hash bin.
Claim 13
Independent Claim
163 words
A method for quickly retrieving a character of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, the method comprising: receiving an encoding value of a character in said subset of characters; calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin includes an encoding value and a glyph describing a graphic representation of a character; searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; and returning a glyph of said hash bin having an encoding value equal to said encoding value of said character.
Claim 14
Independent Claim
163 words
A method for quickly retrieving a character of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, the method comprising: receiving an encoding value of a character in said subset of characters; calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin includes an encoding value and a glyph describing a graphic representation of a character; searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; and returning a glyph of said hash bin having an encoding value equal to said encoding value of said character.
Claim 15
Dependent Claim
106 words
The method as recited in claim 12, wherein said searching comprises: referencing a first hash bin of said hash bin list as a current hash bin; determining if an encoding value of said current hash bin is equal to said encoding value of said character; assigning said current hash bin to be a next hash bin in said list of hash bins if said encoding value of said current hash bin is not equal to said encoding value of said character; and performing said determining and said assigning until said encoding value of said current hash bin is equal to said encoding value of said character.
Claim 16
Dependent Claim
20 words
The method as recited in claim 12, wherein said set of encoding values comprises the Unicode set of encoding values.
Claim 17
Dependent Claim
19 words
The method as recited in claim 12, wherein said subset of characters comprises characters from at least one language.
Claim 18
Dependent Claim
30 words
The method as recited in claim 15, wherein said at least one language includes at least one from the group comprising: Japanese, Chinese, Korean, Thai, Arabic, Indic, and European languages.
Claim 19
Dependent Claim
24 words
The method as recited in claim 12, wherein said MASK1 constant is 0×0ff, said MASK2 constant is 0×07ff, and said SHIFTVAL constant is 8.
Claim 20
Dependent Claim
20 words
The method as recited in claim 12, wherein said hash table of references comprises 2048 references to hash bin lists.
Claim 21
Dependent Claim
18 words
The method as recited in claim 12, wherein said hash bin further comprises a reference to said glyph.
Claim 22
Dependent Claim
19 words
The method as recited in claim 12, wherein said hash bin list comprises a linked list of hash bins.
Claim 23
Dependent Claim
18 words
The method as recited in claim 12, wherein said hash bin list comprises an array of hash bins.
Claim 24
Dependent Claim
26 words
The method as recited in claim 21, wherein said reference to said hash bin list comprises a count of hash bins in said hash bin list.
Claim 25
Dependent Claim
216 words
A set top box for displaying a character on a television, wherein the character is of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, comprising: a processor configured to execute program instructions; and a memory coupled to said processor configured to store said program instructions, wherein said program instructions comprise: instructions for receiving an encoding value of a character in said subset of characters; instructions for calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; instructions for calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin comprises storage for an encoding value and a glyph describing a graphic representation of said character; instructions for searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; instructions for returning a glyph of said hash bin having an encoding value equal to said encoding value of said character; and instructions for rendering said glyph for display on the television.
Claim 26
Dependent Claim
216 words
A set top box for displaying a character on a television, wherein the character is of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, comprising: a processor configured to execute program instructions; and a memory coupled to said processor configured to store said program instructions, wherein said program instructions comprise: instructions for receiving an encoding value of a character in said subset of characters; instructions for calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2), wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; instructions for calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin comprises storage for an encoding value and a glyph describing a graphic representation of said character; instructions for searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; instructions for returning a glyph of said hash bin having an encoding value equal to said encoding value of said character; and instructions for rendering said glyph for display on the television.
Claim 27
Dependent Claim
22 words
The set top box as recited in claim 23, wherein said set of encoding values comprises the Unicode set of encoding values.
Claim 28
Dependent Claim
21 words
The set top box as recited in claim 23, wherein said subset of characters comprises characters from at least one language.
Claim 29
Dependent Claim
26 words
The set top box as recited in claim 25, wherein said at least one language includes at least one from the group comprising: Japanese, Chinese, Korean.
Claim 30
Dependent Claim
26 words
The set top box as recited in claim 23, wherein said MASK1 constant is 0×0ff, said MASK2 constant is 0×07ff, and said SHIFTVAL constant is 8.
Claim 31
Dependent Claim
22 words
The set top box as recited in claim 23, wherein said hash table of references comprises 2048 references to hash bin lists.
Claim 32
Dependent Claim
28 words
The set top box as recited in claim 23, further comprising instructions for allocating storage for said hash table prior to said allocating storage for a hash bin.
Claim 33
Dependent Claim
204 words
A set top box for displaying a character on a television, wherein the character is of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, comprising: a processor configured to execute program instructions; and a memory coupled to said processor configured to store said program instructions, wherein said program instructions comprise: instructions for receiving an encoding value of a character in said subset of characters; instructions for calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2); wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; instructions for calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin includes an encoding value and a glyph describing a graphic representation of said character; instructions for searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; and instructions for returning a glyph of said hash bin having an encoding value equal to said encoding value of said character.
Claim 34
Dependent Claim
204 words
A set top box for displaying a character on a television, wherein the character is of a subset of characters from a set of characters, wherein the set of characters are encoded according to a set of encoding values, wherein each of the characters has a unique associated encoding value, comprising: a processor configured to execute program instructions; and a memory coupled to said processor configured to store said program instructions, wherein said program instructions comprise: instructions for receiving an encoding value of a character in said subset of characters; instructions for calculating an index according to an equation, index=((((encoding.sub.-- value & MASK1)>>SHIFTVAL) encoding.sub.-- value) & MASK2); wherein said MASK1, MASK2, and SHIFTVAL are predefined constants; instructions for calculating a reference to a hash bin list by indexing into a hash table of references to hash bin lists using said index, wherein a hash bin includes an encoding value and a glyph describing a graphic representation of said character; instructions for searching said hash bin list for a hash bin having an encoding value equal to said encoding value of said character; and instructions for returning a glyph of said hash bin having an encoding value equal to said encoding value of said character.
Claim 35
Dependent Claim
118 words
The set top box as recited in claim 30, wherein said instructions for searching comprise: instructions for referencing a first hash bin of said hash bin list as a current hash bin; instructions for determining if an encoding value of said current hash bin is equal to said encoding value of said character; instructions for assigning said current hash bin to be a next hash bin in said list of hash bins if said encoding value of said current hash bin is not equal to said encoding value of said character; and instructions for perforning said determining and said assigning until said encoding value of said current hash bin is equal to said encoding value of said character.
Claim 36
Dependent Claim
22 words
The set top box as recited in claim 30, wherein said set of encoding values comprises the Unicode set of encoding values.
Claim 37
Dependent Claim
21 words
The set top box as recited in claim 30, wherein said subset of characters comprises characters from at least one language.
Claim 38
Dependent Claim
26 words
The set top box as recited in claim 33, wherein said at least one language includes at least one from the group comprising: Japanese, Chinese, Korean.
Claim 39
Dependent Claim
26 words
The set top box as recited in claim 30, wherein said MASK1 constant is 0×0ff, said MASK2 constant is 0×07ff, and said SHIFTVAL constant is 8.
Claim 40
Dependent Claim
22 words
The set top box as recited in claim 30, wherein said hash table of references comprises 2048 references to hash bin lists.
References Cited (Backward Citations)
US4700322A
Cited
US5519443A
Cited
US5294982A
Cited
US5416898A
Cited
US5664086A
Cited
WO1995015654A1
Cited
US5526477A
Cited
WO1995028799A1
Cited
WO1995031069A1
Cited
US5734388A
Cited
US5623593A
Cited
US5570134A
Cited
US5706462A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |