# US 11,030,121 B2 · Apparatus and method for comparing regions associated with first and second bounded pointers > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,030,121 B2 - Document ID: US11030121B2 - Status: Granted - Kind: B2 - Application number: 16/055,240 - Filed: 2018-08-06 - Published: 2020-02-06 - Granted: 2021-06-08 - Earliest claimed: 2018-08-06 - Assignees: Arm Limited - Applicants: Arm Limited - Inventors: Daniel Arulraj; Lee Evan Eisen; Graeme Peter Barnes - Web page: https://patentgrep.com/patent/US11030121B2 ## CPC - G06F 12/1441: {for a range} - G06F 9/30007: {to perform operations on data operands} - G06F 9/3004: {to perform operations on memory} - G06F 9/3012: {Organisation of register space, e.g. banked or distributed register file} - G06F 9/342: {Extension of operand address space} - G06F 9/35: Indirect addressing - G06F 12/00: Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06) - G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing} - G06F 12/0284: {Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163)} - G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)} - G06F 12/04: Addressing variable-length words or parts of words - G06F 12/06: Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence) - G06F 12/0615: {Address space extension} - G06F 12/1483: {using an access-table, e.g. matrix or list} - G06F 21/52: during program execution, e.g. stack integrity {; Preventing unwanted data erasure; Buffer overflow} - G06F 2212/1016: Performance improvement - G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc - G06F 2212/1052: Security improvement - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An apparatus and method are provided for comparing regions associated with first and second bounded pointers to determine whether the region defined for the second bounded pointer is a subset of the region defined for the first bounded pointer. Each bounded pointer has a pointer value and associated upper and lower limits identifying the memory region for that bounded pointer. The apparatus stores first and second bounded pointer representations, each representation comprising a pointer value having p bits, and identifying the upper and lower limits in a compressed form by identifying a lower limit mantissa of q bits, an upper limit mantissa of q bits and an exponent value e. A most significant p−q−e bits of the lower limit and the upper limit is derivable from the most significant p−q−e bits of the pointer value. Mapping circuitry is used to map the lower limit mantissas and upper limit mantissas of the first and second bounded pointer representations to a q+x bit address space comprising 2x regions of size 2n1, where n1 is the value of n determined when using the exponent value of the first bounded pointer representation. Mantissa extension circuitry extends the lower limit and upper limit mantissas for each bounded pointer representation to create extended lower limit and upper limit mantissas comprising q+x bits, where a most significant x bits of each extended limit mantissa are mapping bits identifying which region the associated limit mantissa is mapped to. The determination circuitry then determines whether the region for the second pointer is a subset of the region for the first bounded pointer by comparing the extended lower and upper limit mantissas. ## Claims ### Claim 1 An apparatus to determine whether an accessible memory region defined for a second bounded pointer is a subset of an accessible memory region defined for a first bounded pointer, each bounded pointer having a pointer value and associated upper and lower limits identifying the accessible memory region for that bounded pointer, the apparatus comprising: storage circuitry to store a first bounded pointer representation and a second bounded pointer representation, each bounded pointer representation comprising a pointer value having p bits, and identifying the upper and lower limits in a compressed form by identifying a lower limit mantissa of q bits, an upper limit mantissa of q bits and an exponent value e, where the lower limit and the upper limit each have p bits, and where a most significant p−q−e (p minus q minus e bits) bits of the lower limit and the upper limit is derivable from the most significant p−q−e bits of the pointer value such that the upper and lower limits are anchored by the pointer value to reside within a memory region of size 2n, where n=q+e, where the least significant n bits of the upper limit is derivable from the q bits of the upper limit mantissa and the exponent value e, and where the least significant n bits of the lower limit is derivable from the q bits of the lower limit mantissa and the exponent value e; mapping circuitry to map the lower limit mantissas and the upper limit mantissas of the first and second bounded pointer representations to a q+x bit address space comprising 2x regions of size 2n1, where n1 is the value of n determined when using the exponent value of the first bounded pointer representation, and q+x is less than p; mantissa extension circuitry to extend the lower limit mantissas in the q+x bit address space and the upper limit mantissas in the q+x bit address space for each bounded pointer representation to create extended lower limit and upper limit mantissas comprising q+x bits, where a most significant x bits of each extended limit mantissa are mapping bits identifying which region the associated limit mantissa is mapped to; and determination circuitry to determine whether the accessible memory region defined for the second bounded pointer is a subset of the accessible memory region defined for the first bounded pointer by comparing the extended lower limit and upper limit mantissas for the first and second bounded pointers. ### Claim 2 (depends on 1) An apparatus as claimed in claim 1, wherein x is 2, such that the q+x bit address space comprises 4 regions of size 2n1. ### Claim 3 (depends on 1) An apparatus as claimed in claim 1, wherein the mapping circuitry comprises: difference determination circuitry to determine a difference value identifying a difference between the most significant p−q−e1 bits of the pointer value of the first bounded pointer and the corresponding most significant bits of the pointer value of the second bounded pointer, where e1 is the exponent value of the first bounded pointer representation; and evaluation circuitry to perform a boundary check operation to evaluate whether an adjustment of any of the lower and upper limit mantissas for the first and second bounded pointer is required, wherein the pointer value of the first bounded pointer is anchored to a chosen region from the 2x regions, and the evaluation of the lower and upper limit mantissas for the first bounded pointer determines whether either of those lower and upper limit mantissas should be mapped to the chosen region or to an adjacent region to the chosen region; wherein the mapping circuitry is arranged to determine which of the 2x regions each upper and lower limit mantissa is mapped to in dependence on the difference value and the evaluation made by the evaluation circuitry. ### Claim 4 (depends on 3) An apparatus as claimed in claim 3, wherein: x is 2, such that the q+x bit address space comprises 4 regions of size 2n1; the chosen region is identified by mapping bits “01”, and the mapping bits produced for each of the upper limit mantissa and lower limit mantissa for the first bounded pointer are one of “00”, “01” or “10”, depending on the evaluation performed by the evaluation circuitry. ### Claim 5 (depends on 3) An apparatus as claimed in claim 3, wherein: the pointer value of the second bounded pointer is anchored to a determined region, where the relationship between the determined region and the chosen region is dependent on the difference value; and the evaluation of the lower and upper limit mantissas for the second bounded pointer determines whether either of those lower and upper limit mantissas should be mapped to the determined region or to an adjacent region to the determined region. ### Claim 6 (depends on 3) An apparatus as claimed in claim 3, wherein when the difference value exceeds a predetermined value, the mapping circuitry is arranged to issue a fail trigger to the determination circuitry to cause the determination circuitry to output a check fail signal identifying that the accessible memory region defined for the second bounded pointer is not a subset of the accessible memory region defined for the first bounded pointer. ### Claim 7 (depends on 3) An apparatus as claimed in claim 3, wherein in the event that the mapping circuitry determines that at least one of the lower and upper limit mantissas for the second bounded pointer map to a region other than one of the 2x regions, the mapping circuitry is arranged to issue a fail trigger to the determination circuitry to cause the determination circuitry to output a check fail signal identifying that the accessible memory region defined for the second bounded pointer is not a subset of the accessible memory region defined for the first bounded pointer. ### Claim 8 (depends on 3) An apparatus as claimed in claim 3, wherein: the evaluation circuitry is configured, for each of the first and second bounded pointers, to determine a pointer mantissa for the pointer value by right shifting the pointer value based on the exponent value of the first bounded pointer representation to produce a shifted pointer value, and then taking a least significant q bits of the shifted pointer value to form the pointer mantissa. ### Claim 9 (depends on 8) An apparatus as claimed in claim 8, wherein: the evaluation circuitry is configured to evaluate, for each bounded pointer, the location of the lower limit mantissa, the upper limit mantissa, and the pointer mantissa relative to a representative value less than the lower limit mantissa, in order to determine whether an adjustment of the lower limit mantissa or the upper limit mantissa is required. ### Claim 10 (depends on 9) A data processing apparatus according to claim 9, wherein: for each bounded pointer, the representative value is equal to the lower limit mantissa of that bounded pointer minus 212. ### Claim 11 (depends on 1) An apparatus as claimed in claim 1, further comprising: exponent evaluation circuitry to determine whether the exponent value of the first bounded pointer representation is equal to or greater than the exponent value of the second bounded pointer representation; wherein when the exponent value of the first bounded pointer representation is determined to be less than the exponent value of the second bounded pointer representation, the exponent evaluation circuitry is arranged to issue a fail trigger to the determination circuitry to cause the determination circuitry to output a check fail signal identifying that the accessible memory region defined for the second bounded pointer is not a subset of the accessible memory region defined for the first bounded pointer. ### Claim 12 (depends on 11) An apparatus as claimed in claim 11, further comprising: limit mantissa adjustment circuitry responsive to the exponent value of the first bounded pointer representation being determined to be greater than the exponent value of the second bounded pointer representation, to create altered lower limit and upper limit mantissas for the second bounder pointer for input to the mapping circuitry, the altered lower limit and upper limit mantissas being created taking into account the difference in the exponent values of the first and second bounded pointer representations. ### Claim 13 (depends on 12) An apparatus as claimed in claim 12, wherein a value d is equal to the difference in the exponent values of the first and second bounded pointer representations, and each altered limit mantissa comprises a first portion formed of d least significant bits of the most significant p−q−e2 bits of the pointer value of the second bounded pointer, where e2 is the exponent value of the second bounded pointer representation, and a second portion formed of q−d most significant bits of the original limit mantissa. ### Claim 14 A method of determining whether an accessible memory region defined for a second bounded pointer is a subset of an accessible memory region defined for a first bounded pointer, each bounded pointer having a pointer value and associated upper and lower limits identifying the accessible memory region for that bounded pointer, the method comprising: storing a first bounded pointer representation and a second bounded pointer representation, each bounded pointer representation comprising a pointer value having p bits, and identifying the upper and lower limits in a compressed form by identifying a lower limit mantissa of q bits, an upper limit mantissa of q bits and an exponent value e, where the lower limit and the upper limit each have p bits, and where a most significant p−q−e bits (p minus q minus e bits) of the lower limit and the upper limit is derivable from the most significant p−q−e bits of the pointer value such that the upper and lower limits are anchored by the pointer value to reside within a memory region of size 2n, where n=q+e, where the least significant n bits of the upper limit is derivable from the q bits of the upper limit mantissa and the exponent value e, and where the least significant n bits of the lower limit is derivable from the q bits of the lower limit mantissa and the exponent value e; employing mapping circuitry to map the lower limit mantissas and the upper limit mantissas of the first and second bounded pointer representations to a q+x bit address space comprising 2x regions of size 2n1, where n1 is the value of n determined when using the exponent value of the first bounded pointer representation, and q+x is less than p; extending the lower limit mantissas in the q+x bit address space and the upper limit mantissas in the q+x bit address space for each bounded pointer representation to create extended lower limit and upper limit mantissas comprising q+x bits, where a most significant x bits of each extended limit mantissa are mapping bits identifying which region the associated limit mantissa is mapped to; and employing determination circuitry to determine whether the accessible memory region defined for the second bounded pointer is a subset of the accessible memory region defined for the first bounded pointer by comparing the extended lower limit and upper limit mantissas for the first and second bounded pointers. ### Claim 15 An apparatus for determining whether an accessible memory region defined for a second bounded pointer is a subset of an accessible memory region defined for a first bounded pointer, each bounded pointer having a pointer value and associated upper and lower limits identifying the accessible memory region for that bounded pointer, the apparatus comprising: storage means for storing a first bounded pointer representation and a second bounded pointer representation, each bounded pointer representation comprising a pointer value having p bits, and identifying the upper and lower limits in a compressed form by identifying a lower limit mantissa of q bits, an upper limit mantissa of q bits and an exponent value e, where the lower limit and the upper limit each have p bits, and where a most significant p−q−e bits (p minus q minus e bits) of the lower limit and the upper limit is derivable from the most significant p−q−e bits of the pointer value such that the upper and lower limits are anchored by the pointer value to reside within a memory region of size 2n, where n=q+e, where the least significant n bits of the upper limit is derivable from the q bits of the upper limit mantissa and the exponent value e, and where the least significant n bits of the lower limit is derivable from the q bits of the lower limit mantissa and the exponent value e; mapping means for mapping the lower limit mantissas and the upper limit mantissas of the first and second bounded pointer representations to a q+x bit address space comprising 2x regions of size 2n1, where n1 is the value of n determined when using the exponent value of the first bounded pointer representation, and q+x is less than p; mantissa extension means for extending the lower limit mantissas in the q+x bit address space and the upper limit mantissas in the q+x bit address space for each bounded pointer representation to create extended lower limit and upper limit mantissas comprising q+x bits, where a most significant x bits of each extended limit mantissa are mapping bits identifying which region the associated limit mantissa is mapped to; and determination means for determining whether the accessible memory region defined for the second bounded pointer is a subset of the accessible memory region defined for the first bounded pointer by comparing the extended lower limit and upper limit mantissas for the first and second bounded pointers.