News Column

Researchers Submit Patent Application, "Blank Bit and Processor Instructions Employing the Blank Bit", for Approval

August 27, 2014



By a News Reporter-Staff News Editor at Electronics Newsweekly -- From Washington, D.C., VerticalNews journalists report that a patent application by the inventor Yearsley, Gyle D. (Boise, ID), filed on April 8, 2014, was made available online on August 14, 2014.

The patent's assignee is IXYS CH GmbH.

News editors obtained the following quote from the background information supplied by the inventors: "Processors (for example, microprocessors and microcontrollers) are commonly employed to perform tasks involving strings of character values. One such task is to compare two strings of character values, and to return one value (for example, a zero) if the two strings are determined to be the same but to return another value (for example, a one) if the two strings are determined to be different. Each character value may, for example, be an eight-bit ASCII character value that represents a character. A binary ASCII value of '01001000' represents a capital 'H' character. A binary ASCII value of '01000101' represents a capital 'E' character. A binary ASCII value of '01001100' represents a capital 'L' character. A binary ASCII value of '01001111' represents a capital 'O' character. A binary ASCII value of '00000000' represents a special ASCII character called the 'NULL' character. The NULL character value is placed at the end of the string of character values where the string is stored in memory to delineate the end of the character string.

"Consider an example in which a program executing on a processor is to read character values out of memory and to determine whether the character values are a certain string of character values. FIG. 1 (Prior Art) illustrates a portion of a C language program that performs a string compare task. Line 10 indicates that a first string of characters values (representing the character string 'HELLO') is pointed to by a first pointer HTSTR1. This pointer points to the location in memory where the first eight-bit ASCII character value of the first string HTSTR1 is found. Character values of the first string are stored in corresponding string of adjacent memory locations. A NULL character value ('00000000') is present at the end of the string of memory locations after the last character value representing the capital 'O'. This NULL character value indicates the end of the first string of character values.

"Line 11 indicates that a second string of characters values (representing the character string 'HELLO') is pointed to by a second pointer HTSTR2. This second pointer points to the location in memory where the first character value of the second string is found. The end of the second string is also marked by a NULL character value ('00000000').

"Line 12 calls a string compare function 'STRCMP'. The STRCMP function compares the first string pointed to by the pointer HTSTR1 to the second string pointed to by the pointer HTSTR2. If the two strings are equal, then the value of the function is zero, otherwise the value of the function is one. The value of the function is assigned to the digital value ERROR. Accordingly, ERROR is set to zero if the two strings match, whereas ERROR is set to one if the two strings do not match.

"The string compare task is so commonly needed that a programmer does not typically need to write code to perform the string compare operation. Rather, the programmer writes the STRCMP function call into the C program where a string compare is needed. When the C program is compiled, the C compiler supplies the STRCMP function with a previously written and compiled portion of machine code which, when executed, performs the string compare function.

"FIG. 2 (Prior Art) illustrates an amount of assembly code, which when compiled and executed, carries out the STRCMP function of FIG. 1. Line 13 is a label 'STRCMP'. Line 14 loads register R0 of a processor with the pointer HTSTR1. This pointer points to the memory location where the first character value of the first string is stored. Line 15 loads register R1 of the processor with the pointer HTSTR2. This pointer points to the memory location wherein the second character value of the second string is stored. Line 16 is a label for LOOP. Line 17 obtains the pointer HTSTR1 out of register R0, retrieves the content of the memory location pointed to by the pointer, and loads that value into register R2. After the load, the LD instruction automatically increments the content of R0. After execution of the LD instruction, register R0 therefore contains a pointer that points to the location in memory where the second character value of the first string is stored.

"The LD instruction of line 18 is similar to the instruction of line 17. The pointer HTSTR2 out of register R1 retrieves the content of the memory location pointed to by the pointer, and loads the value into register R3. Then the pointer value in R1 is incremented so that the content of R1 points to the second character of the second string in memory.

"Line 19 is the compare to zero instruction CPZ that takes a single operand, in this case the content of register R2. Execution of the CPZ instruction compares the content of register R2 to zero. If the result is true (the content of register R2 is zero), then the CPZ instruction sets a zero bit ('Z') in a flag register in the processor. Otherwise, the zero bit is cleared. In the present example, the first character of the first string (see line 10) is 'H'. Execution of line 17 loaded a digital '01001000' into register R2. The compare to zero of line 19 therefore compares '01001000' to '00000000', and does not set the zero bit. The zero bit is therefore a digital zero (i.e., cleared).

"Next, line 20 causes program execution to jump to the label 'DONE' if the zero bit is true (i.e., is set). In the present example, the first character of the first character string was not a NULL character, so the zero bit was not set in line 19, and program execution does not jump to the DONE label.

"Next, line 21 compares the content of register R3 to zero and sets the zero bit if the content of register R3 is zero. In the present example, the first character of the second character string is not a NULL character. The compare of line 21 does not result in the zero bit being set. Line 22 therefore does not result in program execution jumping to the DONE label. It is therefore seen that the instructions of lines 19-22 check to make sure that one of the first character values of the two strings is not '00000000'. If one of the first character values is '00000000', then program execution is made to jump to the DONE label.

"Next, line 23 causes the ASCII value of the first character of the first string in register R2 to be subtracted from the ASCII value of the first character of the second string in register R3. If the result is zero, then the zero bit ('Z') in the flag register is set, otherwise it is cleared. In the present example, the first character of the first string is 'H' and the first character of the second string is 'H'. The content of register R2 is therefore a digital '01001000' and the content of register R3 is a digital '01001000'. The SUB instruction of line 23 therefore sets the zero bit in the flag register.

"Next, line 24 causes program execution to jump back to the label 'LOOP' if the zero bit is set (the first character values of the two strings are identical). Otherwise, the zero bit is cleared, and no jump is taken. In the present example, the SUB instruction of line 23 set the zero bit, so the JP instruction of line 24 results in program execution jumping back to the LOOP label.

"In line 17, the pointer in register R0 was incremented at the end of execution of the previous LD instruction of line 17. Accordingly, when program execution jumps back to the LOOP label, register R0 contains a pointer that points to the memory location where the second character value of the first string is stored. Similarly, register R1 contains a pointer that points to the memory location where the second character value of the second string is stored. Therefore, in a second pass through the loop, the second character values of the two strings are tested to see if one of them is the NULL character value, and if neither is then the two character values are compared to see if they match. This process repeats, character value by character value, through the strings.

"When the 'O0000000' character values at the ends of the two strings are loaded into registers R2 and R3, the character value in register R2 is checked in line 19 to see if it is zero. In this case, R2 does contain '00000000'. Program execution jumps to the DONE label. Line 27 subtracts the content of register R2 from the content of register R3. In the present example, R2 contains '00000000' representing the NULL at the end of the first string and R3 contains '00000000' representing the NULL at the end of the second string. The SUB instruction of line 27 places the result of the subtraction in the R2 register, thereby overwriting the content of the R2 register. In the present example, there are ASCII NULL character values terminating both strings. The subtraction of line 27 therefore results in a zero being placed in register R2.

"Next, the return instruction RET causes program execution to return to the line 12 that called the STRCMP function. If the value in R2 is zero, then the two strings matched. If, on the other hand, the value in R2 is not zero, then when a NULL value ('00000000') was encountered in one string the characters at corresponding locations in the two strings did not match thereby indicating that the two strings did not match.

"Note in the example of FIGS. 1 and 2 that the loop includes two compare to zero CPZ instructions and associated jump JP instructions to test each string for a NULL termination character value. The compare and jump instructions are in lines 19-22. Executing these testing instructions to look for NULL character values consumes processing resources and increases the number of instructions in the loop. Where the strings of character values being compared are long, the loop may be traversed many times. The instructions used to look for the NULL termination values therefore are executed many times and add significantly to the time required to carry out the overall higher level string compare task. An improved processor architecture and instruction set is desired."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventor's summary information for this patent application: "A novel 'blank bit' is added to the flag register of a novel processor. When a novel first instruction (the novel first instruction is an instruction taken from a set of novel instructions including, for example, certain arithmetic instructions, certain logic instructions and certain load instructions) is executed, all operands used by the novel first instruction are checked to see if any of the operands is a NULL character value. Execution of the novel first instruction causes information on the result of the check to be stored in the blank bit. The number of operands checked for the NULL character value depends on the type of the first instruction. For example, if the first instruction is a load instruction that reads one value out of memory and places the retrieved value into a processor register, then only one operand is used by the instruction and only one operand is checked for the NULL character value. If, however, the first instruction is an arithmetic instruction that adds two operands, then two operands are used by the instruction and two operands are checked for the NULL character value.

"Execution of a novel second instruction uses the information stored in the blank bit to determine whether execution of the second instruction should result in a second operation being performed. The novel second instruction may, for example, be a conditional jump operation that only performs a jump if the blank bit stores information indicating that no NULL character value was encountered during execution of the first instruction. By using the novel first and second instructions together in a loop, the number of instructions that the novel processor needs to execute to read in values from memory and to check for NULL values at the end of strings and arrays is small in comparison with the number of instructions a conventional processor needs to execute to do the same read in and NULL character value check tasks. The blank bit and novel first and second instructions are particularly useful in efficiently carrying out string functions such as, for example, string compare functions and string length functions and array value load functions. A program that includes instructions that use the novel blank bit can be stored on any suitable computer-readable or processor-readable medium (for example, semiconductor memory storage medium such as semiconductor RAM and ROM and FLASH and EPROM and EEPROM, magnetic storage medium devices such as tape drives and hard disc drives, and optical storage medium devices such as compact discs (CDs) and digital video discs (DVDs)).

"Other embodiments, methods and advantages are described in the detailed description below. This summary does not purport to define the invention. The invention is defined by the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

"The accompanying drawings, where like numerals indicate like components, illustrate embodiments of the invention.

"FIG. 1 (Prior Art) is a listing of an amount of C language code that uses a string compare function.

"FIG. 2 (Prior Art) is a listing of an amount of assembly code which, when compiled and linked and executed, performs the string compare task of the string compare function of FIG. 1.

"FIG. 3 is a diagram that illustrates two strings of character values. Each string is terminated by a NULL character value.

"FIG. 4 is a listing of an amount of C language code that uses a string compare function. The string compare function compares the strings of character values of FIG. 3.

"FIG. 5 is a listing of an amount of assembly code which, when compiled and linked and executed, performs the string compare task of the string compare function of FIG. 1. The code of FIG. 5 employs an instruction that sets and clears the novel 'blank bit'. The code of FIG. 5 also employs a conditional jump instruction that performs the jump operation if the 'blank bit' contains a particular Boolean value.

"FIG. 6 is a simplified block diagram of a processor that executes the code of FIGS. 4 and 5.

"FIG. 7 is a more detailed diagram that illustrates the 'blank bit' in the flag register of the processor of FIG. 6.

"FIG. 8 is a table that compares the number of clock cycles required to perform a string compare task using a conventional processor (that executes the code of FIGS. 1 and 2) to the number of clock cycles required to perform a string compare task using the novel processor of FIG. 6 (that executes the code of FIGS. 4 and 5).

"FIG. 9 lists a number of instructions that set and clear the novel 'blank bit'.

"FIG. 10 is a flowchart of a novel method employing the novel 'blank bit' and employing instructions that use the novel 'blank bit'."

For additional information on this patent application, see: Yearsley, Gyle D. Blank Bit and Processor Instructions Employing the Blank Bit. Filed April 8, 2014 and posted August 14, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=482&p=10&f=G&l=50&d=PG01&S1=20140807.PD.&OS=PD/20140807&RS=PD/20140807

Keywords for this news article include: Electronics, IXYS CH GmbH, Semiconductor.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Electronics Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters