METHOD AND SYSTEM FOR FAST 90 DEGREE ROTATION OF ARRAYS

• US 20090189918A1
• Filed: 03/30/2009
• Published: 07/30/2009
• Est. Priority Date: 08/27/2004
• Status: Active Grant

• Current Assignee: Ian R. Ollmann
• Original Assignee: Ian R. Ollmann
• Inventors: Ollmann, Ian R.
• Granted Patent: US 7,768,531 B2
• Time in Patent Office: Days
• US Class Current: 345/658
• CPC Class Codes: G06T 3/606 by memory addressing or mapping
• CPC Class Codes: G09G 2340/0492 Change of orientation of the displayed image, e.g. upside-down, mirrored
• CPC Class Codes: G09G 2360/123 using interleaving
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory
• CPC Class Codes: G09G 5/395 Arrangements specially adapted for transferring the contents of the bit-mapped memory to the screen G09G5/399 takes precedence

Abstract

A method and system to rotate a 2^N by 2^N array are described. Consistent with one embodiment of the present invention, the 2^N elements of the 2^N rows of a 2^N by 2^N array are loaded from memory into the vector registers of a processor'"'"'s single instruction multiple data (SIMD) unit. Next, the elements of the rows in the top half of the array are interleaved with corresponding elements from a corresponding row in the bottom half of the array. The loading and interleaving operations are repeated N times before the results, stored in the vector registers, are written back to memory.

Claims

1. A computer-implemented method to rotate a 2^N by 2^N array in the counter-clockwise direction, the computer-implemented method comprising:

loading 2^N elements of each row of the array into vector registers of a SIMD unit;

interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; and

repeating said loading and interleaving operations a total of N times.

2. The method of claim 1, wherein the interleaving operation includes storing the results of the interleaving operation in vector registers.

3. The computer-implemented method of claim 2, further comprising:

after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2^N elements written to memory representing the bottom row of the rotated array.

4. The method of claim 1, wherein said interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array is performed in parallel.

5. The method of claim 1, wherein the loading and interleaving operations are achieved via the execution of a single vector merge instruction that operates on data in multiple vector registers.

6. The method of claim 1, wherein the 2^N by 2^N array represents a subsection of a digital image and the loading and interleaving operations are performed iteratively on a plurality of subsections to rotate an entire digital image.

7. A computer-implemented method to rotate a 2^N by 2^N array in the clockwise direction, the computer-implemented method comprising:

loading 2^N elements of each row of the array into vector registers of a SIMD unit;

interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array follows an element from a corresponding row in the bottom half of the array; and

repeating said loading and said interleaving operations a total of N times.

8. The method of claim 7, wherein the interleaving operation includes storing the results of the interleaving operation in vector registers.

9. The computer-implemented method of claim 8, further comprising:

after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2^N elements written to memory representing the bottom row of the rotated array.

10. The method of claim 7, wherein said interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array is performed in parallel.

11. The method of claim 7, wherein the loading and interleaving operations are achieved via the execution of a single vector merge instruction that operates on data in multiple vector registers.

12. The method of claim 7, wherein the 2^N by 2^N array represents a subsection of a digital image and the loading and interleaving operations are performed iteratively on a plurality of subsections to rotate an entire digital image.

13. A computer-readable medium storing instructions, which, when executed, cause a computer to perform a method to rotate a 2^N by 2^N array in the counter-clockwise direction, the method comprising:

loading 2^N elements of each row of the array into vector registers of a SIMD unit;

interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array; and

repeating said loading and interleaving operations a total of N times.

14. A computer-readable medium as in claim 13, wherein said interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array includes storing the results of the interleaving operation in vector registers.

15. A computer-readable medium as in claim 14, wherein the method further comprises:

after N loading and N interleaving operations, writing the vector registers storing the results of the N loading and N interleaving operations to memory in order so that the elements representing the top row of the rotated array precede the elements representing each successive row of the array, the last 2^N elements written to memory representing the bottom row of the rotated array.

16. A computer-readable medium as in claim 13, wherein said interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array is performed in parallel.

17. A computer-readable medium as in claim 13, wherein the loading and interleaving operations are achieved via the execution of a single vector merge instruction that operates on data in multiple vector registers.

18. A computer-readable medium as in claim 13, wherein the 2^N by 2^N array represents a subsection of a digital image and said loading and interleaving operations are performed iteratively on a plurality of subsections to rotate an entire digital image.

19. A computer-readable medium storing instructions, which, when executed, cause a computer to perform a method to rotate a 2^N by 2^N array in the clockwise direction, the method comprising:

loading 2^N elements of each row of the array into vector registers of a SIMD unit;

interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array follow an element from a corresponding row in the bottom half of the array; and

repeating said loading and interleaving operations a total of N times.

20. A computer-readable medium as in claim 19, wherein said interleaving the 2^N elements of each row in the top half of the array with the 2^N elements of a corresponding row in the bottom half of the array so that each element from the top half of the array precedes an element from a corresponding row in the bottom half of the array includes storing the results of the interleaving operation in vector registers.