Abstract:
One embodiment of the present invention provides a system for implementing a string object defined in a programming language. Upon receiving characters to be embedded in the string object, the system allocates space for the string object that includes a header, which is appended to a character array of the string object. Next, the system copies the characters into the character array of the string object. The system also initializes the header by initializing a class pointer in the header to point to a class for the string object, and by initializing a length field in the header to specify a length for the string object. In this way, the string object remains compatible with previous implementations of the string object that use a character array that is separate from the string object.

Description:
RELATED APPLICATION  
       [0001]    This application hereby claims priority under 35 U.S.C. §119 to U.S. Provisional Patent Application No. 60/392,375, filed on Jun. 26, 2002, entitled “Optimizing Platform Independent Code,” by inventors Nicholas Shaylor and Douglas Simon and to U.S. Provisional Patent Application No. 60/412,607, filed on Sep. 20, 2002, entitled “The Squawk System,” by inventors Nicholas Shaylor and Douglas Simon. 
     
    
     
       BACKGROUND  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates to programming languages. More specifically, the present invention relates to a method and an apparatus for implementing string objects defined within a programming language.  
           [0004]    2. Related Art  
           [0005]    Dramatic advances in computer technology presently make it possible to integrate a significant amount of computing power onto “smart cards.” Smart cards are presently used in a variety of applications that solve common security and identity needs. For example, smart cards have been integrated into credit cards, debit cards, corporate badges, and even cell phones.  
           [0006]    New smart card designs can accommodate larger amounts of memory, for example, new smart card designs can accommodate up to 160K bytes of read-only memory (ROM), 64K bytes of electrically erasable programmable read-only memory (EEPROM), and 8K bytes of random access memory (RAM). These larger amounts of memory make it possible to integrate more functionality into a smart card. In particular, the additional memory can be used to implement a virtual machine, such as the JAVA™ virtual machine (JVM), in a smart card, and to allow the use of objects defined within an object-oriented programming system. (JAVA is a trademark of SUN Microsystems, Inc. of Santa Clara, Calif.) Integrating a virtual machine into a smart card enables the smart card execute a large number of platform-independent applications. Moreover, the associated development environment for the virtual machine can simplify the process of developing applications for smart cards.  
           [0007]    While it is possible to implement a virtual machine on one of these smart cards, the memory is still quite limited compared to a typical desktop computer system. This limited memory leads to many challenges in the implementing an object-oriented programming system.  
           [0008]    For example, FIG. 1 depicts an implementation of a string object as commonly implemented in the JAVA programming language. This implementation includes two parts: a string object  102  and a character array  114 . Note that strings may be represented in this manner in programming languages and systems other than “object-oriented” systems.  
           [0009]    String object  102  includes a class pointer  104 , an array pointer  106 , an offset  108 , and a length  110 . Class pointer  104  points to string class  112  and thereby identifies string object  102  as belonging to string class  112 . Array pointer  106  points to the beginning of array of characters  122  within character array  114 . Offset  108  points to the beginning of a sub-string  124  within array of characters  122 . Finally, length  110  specifies the length of sub-string  124 .  
           [0010]    Character array  114  includes a length  116 , a class pointer  118 , and an array of characters  122 . Class pointer  118  points to character class  120 , which indicates that the object is a character array  114 . Typically, characters in character array  114  are stored as sixteen-bit UNICODE™ characters. UNICODE is a trademark or registered trademark of UNICODE, Inc. Length  116  describes the length of the string in array of characters  122 .  
           [0011]    The implementation described above requires a minimum of twenty-eight bytes to store a single character-sixteen for string object  102  and twelve for character array  114 . While using this amount of storage on a desktop machine with large amounts of memory might be acceptable, using this amount of storage on a small computing device, such as a smart card, or a computing device such as a web server that handles a large number of strings, needlessly reduces the available memory on these devices.  
           [0012]    Hence, what is needed is a method and an apparatus for implementing string objects in a programming language without using an excessive amount of memory.  
         SUMMARY  
         [0013]    One embodiment of the present invention provides a system for implementing a string object defined in a programming language. Upon receiving characters to be embedded in the string object, the system allocates space for the string object that includes a header, which is appended to a character array of the string object. Next, the system copies the characters into the character array of the string object. The system also initializes the header by initializing a class pointer in the header to point to a class for the string object, and by initializing a length field in the header to specify a length for the string object. In this way, the string object remains compatible with previous implementations of the string object that use a character array that is separate from the string object.  
           [0014]    In a variation of this embodiment, characters within the string buffer are encoded in a sixteen-bit standard character code.  
           [0015]    In a further variation, characters within the string buffer are encoded in an eight-bit standard character code.  
           [0016]    In a further variation, characters within the string buffer are encoded in a variable-length standard character code.  
           [0017]    In a further variation, the string buffer is created by first assuming that characters to be added to the string buffer can be encoded in an eight-bit representation.  
           [0018]    In a further variation, if characters are encountered that will not fit in the eight-bit representation, the string buffer is converted to use a sixteen-bit representation.  
           [0019]    In a further variation, the string buffer is converted to use a variable-length representation to save storage space.  
           [0020]    In a further variation, a class pointer is moved to convert the character array into a string object instead of copying the string object.  
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0021]    [0021]FIG. 1 illustrates a typical string object implementation for the JAVA programming language.  
         [0022]    [0022]FIG. 2 illustrates a computer system in accordance with an embodiment of the present invention.  
         [0023]    [0023]FIG. 3 illustrates a string object encoded in a sixteen-bit character code in accordance with an embodiment of the present invention.  
         [0024]    [0024]FIG. 4 illustrates a string object encoded in an eight-bit character code in accordance with an embodiment of the present invention.  
         [0025]    [0025]FIG. 5 illustrates a string object encoded in a variable-length character code in accordance with an embodiment of the present invention.  
         [0026]    [0026]FIG. 6 illustrates an alternate string object encoding method in accordance with an embodiment of the present invention.  
         [0027]    [0027]FIG. 7 is a flowchart illustrating the process of creating a string object in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0028]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0029]    The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet.  
         [0030]    Computer System  
         [0031]    [0031]FIG. 2 illustrates a computer system  202  in accordance with an embodiment of the present invention. Computer system  202  can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. As is illustrated in FIG. 2, computer system  202  includes object-oriented programming system  204  and object storage  208 . Object storage  208  includes string buffer  206 . Note that the system applies equally to programming systems other than object-oriented programming systems. Only object-oriented systems will be described herein.  
         [0032]    Object-oriented programming system  204  can for example include a JAVA virtual machine or any other object-oriented programming system. Object-oriented programming system  204  executes application programs that operate on objects. In doing so, object-oriented programming system  204  uses string buffer  206  to store temporary data, for example, during string object construction. Object storage  208  is used to store objects such as string buffer  206  and string objects.  
         [0033]    During operation, object-oriented programming system  204  creates a string object by first creating string buffer  206 . Once string buffer  206  has been created and initialized, string buffer  206  is transformed into a string object within object storage  208 . This process is described in more detail below in conjunction with FIG. 7.  
         [0034]    Sixteen-Bit Encoding  
         [0035]    [0035]FIG. 3 illustrates a string object  300  encoded using a sixteen-bit character code in accordance with an embodiment of the present invention. String object  300  includes class pointer  302 , length  304 , encoding type  306 , and UNICODE character array  308 .  
         [0036]    Class pointer  302  points to string class  112 , thereby identifying object  300  as belonging to string class  112 . This maintains compatibility with the string object implemented using a separate character array described above with reference to FIG. 1. Note, however, that the system does not allocate memory for string object  102  as illustrated in FIG. 1. This reduces the memory footprint of string object  300  in comparison to the implementation illustrated in FIG. 1.  
         [0037]    Length  304  specifies the length of string object  300  while encoding type  306  specifies the encoding type for characters within string object  300 . For example, the encoding type for string object  300  is the 16-bit UNICODE character encoding. The characters for the string are stored as illustrated in UNICODE character array  308 .  
         [0038]    Eight-Bit Encoding  
         [0039]    [0039]FIG. 4 illustrates a string object  400  encoded in an eight-bit character code in accordance with an embodiment of the present invention. String object  400  includes class pointer  402 , length  404 , encoding type  406 , and BYTE character array  408 .  
         [0040]    Class pointer  402  points to string class  112 , thereby identifying object  400  as belonging to string class  112 . This maintains compatibility with the string object implemented using a separate character array described above with reference to FIG. 1. Note, however, that the system does not allocate memory for string object  102  as illustrated in FIG. 1. This reduces the memory footprint of string object  400  in comparison to the implementation illustrated in FIG. 1.  
         [0041]    Length  404  specifies the length of string object  400  while encoding type  406  specifies the encoding type for the characters within string object  400 . In this example, the encoding type for string object  400  is BYTE character encoding. Hence, the characters of the string are stored as illustrated in BYTE character array  408 . Note that using a BYTE character representation can greatly reduce the amount of space allocated to a given string object.  
         [0042]    Variable Length Encoding  
         [0043]    [0043]FIG. 5 illustrates a string object  500  encoded in a variable length character code in accordance with an embodiment of the present invention. String object  500  includes class pointer  502 , length  504 , encoding type  506 , and, for example, UTF-8 character array  508 . Other variable length encoding schemes can be used.  
         [0044]    Class pointer  502  points to string class  112 , thereby identifying object  500  as belonging to string class  112 . This maintains compatibility with the string object implemented using a separate character array described above with reference to FIG. 1. Note, however, that the system does not allocate memory for string object  102  as illustrated in FIG. 1. This reduces the memory footprint of string object  500  in comparison to the implementation illustrated in FIG. 1.  
         [0045]    Length  504  specifies the length of string object  500  while encoding type  506  specifies the encoding type for the characters within string object  500 . The encoding type for string object  500  is UTF-8 character encoding-a variable length character encoding. The characters of the string are stored as illustrated in UTF-8 character array  508 .  
         [0046]    Note that using a UTF-8 character representation can provide a savings in the number of bytes allocated to a given string object as compared to a Unicode representation. Also note that using the variable length character encoding requires greater computation time to extract a given character from UTF-8 character array  508 . As is illustrated in FIG. 5, characters in the variable-length character encoding can be encoded using one, two, or, three bytes. Note that other encodings are possible as well.  
         [0047]    Alternate Encoding Method  
         [0048]    [0048]FIG. 6 illustrates alternative string object encoding methods in accordance with an embodiment of the present invention. Note that these alterative encoding methods do not use an encoding bit. Instead, three different instances of the string class  112  are provided (byte array string class  601 , Unicode string class  602 , and UTF-8 string class  603 ). These are referenced by byte character array  604 , Unicode character array  606  and UTF-8 character array  608 , respectively.  
         [0049]    Byte character array  604  includes a set of bytes that encode character values, as well as a length  610  for byte character array  604 , and a class pointer  609 , which points to byte array string class  601 .  
         [0050]    Similarly, Unicode character array  606  includes a set of 16-bit Unicode symbols that encode character values, as well as a length  612  for Unicode character array  606 , and a class pointer  611 , which points to Unicode array string class  602 .  
         [0051]    Finally, UTF-8 character array  606  includes a set of variable length UTF-8 symbols that encode the character values, as well as a length  614  for UTF-8 character array  608 , and a class pointer  613 , which points to UTF-8 array string class  106 .  
         [0052]    Creating a String Object  
         [0053]    [0053]FIG. 7 is a flowchart illustrating the process of creating a string object in accordance with an embodiment of the present invention. The system starts when characters are received for a string object (step  700 ). Next, the system creates a new string buffer assuming an eight-bit character representation (step  702 ). The system then selects a character to add to the string buffer (step  704 ).  
         [0054]    Next, the system determines if the character will fit in an eight-bit representation (step  706 ). If so, the system adds the character to the string buffer array (step  708 ). After adding the character to the string buffer array, the system determines if there are more characters to be added to the string buffer (step  710 ). If so, the process returns to step  704  to select the next character.  
         [0055]    If the character will not fit in an eight-bit representation at step  706 , the system changes the string buffer array from an eight-bit representation to a sixteen-bit representation (step  712 ). After each of the characters within the string buffer array have been converted from an eight-bit representation to a sixteen-bit representation, the system adds the character to the string buffer array (step  714 ). Next, the system determines if there are more characters to add to the string buffer array (step  716 ). If so, the system retrieves the next character to add to the string buffer array (step  718 ) and the process returns to step  714  to add the character to the string buffer array.  
         [0056]    When there are no more characters at step  716 , the system can optionally calculate whether a variable length encoding such as UTF-8 would use storage space more efficiently (step  717 ). If so, the system can convert the string buffer array to the variable length encoding (step  719 ).  
         [0057]    When there are no more characters at step  710  or  716 , or optionally, after the possible conversion of the string buffer array into variable length encoding, the system converts the string buffer into a string object and sets the encoding type (step  720 ). In one embodiment of the present invention, this involves moving the class pointer to convert the character array into a string object instead of copying the string object. Finally, the system initializes the class pointer and the length in the string header (step  722 ).  
         [0058]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.