Binary search procedure for control table stored in memory system

An apparatus comprising:

• processing circuitry to perform an operation based on information specified in a control table stored in a memory system, the control table comprising a plurality of entries each specifying a first limit address and one of a second limit address and a size, for identifying limits of a corresponding address region of variable size within an address space, where the plurality of entries are arranged in the control table in order of the first limit address;
• and
• table lookup circuitry to perform a binary search procedure to identify whether the control table comprises an entry corresponding to a query address, the binary search procedure comprising a plurality of search window narrowing steps for narrowing a current search window of candidate entries of the control table to a narrower search window comprising fewer candidate entries;
• in which:
• in a given search window narrowing step, the table lookup circuitry is configured to narrow the current search window based on a comparison of the query address against the first limit address of a selected candidate entry of the current search window, independent of said one of the second limit address and the size of the selected candidate entry;
• and
• following a final search window narrowing step which narrows the current search window to a single candidate entry of the control table, the table lookup circuitry is configured to determine that said single candidate entry is the entry corresponding to the query address when the query address is within the corresponding address region defined by the first limit address and said one of the second limit address and the size of said single candidate entry;
• the apparatus comprising entry storage to store at least one entry,
• where the entry storage comprises one of:
• an entry cache to cache at least one entry of the control table previously obtained from the memory system;
• and
• static register storage to store at least one further entry configurable by a static entry parameter configuration operation, each further entry specifying control information for a corresponding address region of variable size within the address space, for which limits are identified by a first limit address and one of a second limit address and a size,
• in which the table lookup circuitry is configured to limit the current search window for an initial search window narrowing step of the binary search procedure based on information derived from said at least one entry stored in the entry storage.

A non-transitory storage medium storing a computer program for controlling a host data processing apparatus to provide an instruction execution environment for execution of instructions;

• the computer program comprising:
• processing program logic to perform an operation based on information specified in a control table comprising a plurality of entries each specifying a first limit address and one of a second limit address and a size for calculating the second limit address, wherein the first limit address and the second limit address are addresses within a same address space and identify, limits of a corresponding address region of variable size within the address space, where the plurality of entries are arranged in the control table in order of the first limit address, and where encoding of the control table entries permits there to be gaps between the corresponding address regions defined by successive entries of the control table;
• and
• table lookup program logic to perform a binary search procedure to identify whether the control table comprises an entry corresponding to a query address, the binary search procedure comprising a plurality of search window narrowing steps for narrowing a current search window of candidate entries of the control table to a narrower search window comprising fewer candidate entries;
• in which:
• in a given search window narrowing step, the table lookup program logic is configured to narrow the current search window based on a comparison of the query address against the first limit address of a selected candidate entry of the current search window, independent of said one of the second limit address and the size of the selected candidate entry;
• and
• following a final search window narrowing step which narrows the current search window to a single candidate entry of the control table, the table lookup program logic is configured to determine that said single candidate entry is the entry corresponding to the query address in response to the query address being within the corresponding address region defined by the first limit address and said one of the second limit address and the size of said single candidate entry.