Bit Map Stretching Using Operand Routing and Operation Selective Multimedia Extension Unit

1. Field of the Invention

The invention relates to stretching of video bit maps, and more specifically to employing an operand routing and operation selective extension unit to stretch bit maps for video images.

2. Description of the Related Art

The microcomputer industry has seen a metamorphosis in the way computers are used over the last number of years. Originally, most operating systems were text based requiring typed user input and providing textual response. These systems have given way to graphical based environments. Current systems are heavily graphically based, both providing graphical user interfaces including icons, windows, and the like, and providing graphical interaction with a user through a variety of user input devices.

This trend is likely to continue. But graphical, multimedia environments place different and greater demands on processor capabilities than the old textual environments. For many years, the Intel .times.86 series of processors by Intel Corporation has provided the computing power for IBM PC compatible machines. The architecture of the Intel design, however, is not optimized towards graphical operations.

To this end, a number of extensions to the .times.86 architecture have been proposed and developed. These include the MMX extensions developed by Intel Corporation. Further, other manufacturers have similarly extended their instruction sets. For example, Sun Microcomputing has developed the UltraSparc, a graphics extension of the SPARC V9 architecture.

Typical vector processors provide for multiple operations simultaneously, but require that the same operation be performed by each partition within the vector (SIMD, or single instruction multiple data). In the multimedia extension unit architecture, this has changed. Not only can multiple operations be concurrently executed on vectorized data, but different operations can be simultaneously performed, and the vectorized data can be rerouted through a number of multiplexers.

This architecture presents a number of possibilities, but developing algorithms that efficiently utilize this architecture places its own demands, given the new features of the instruction set. It is desirable to efficiently utilize this architecture to execute algorithms for multimedia.

According to the invention, operand routing and selectable operations are used in a multimedia extension unit to perform stretching of a bit map. Two source pixels are simultaneously selected for two destination pixels based on an integer portion of an interpolation value. Further, the next succeeding pixels after the two source pixels are also chosen based on the integer portion of the interpolation value. Then, for each destination pixel, its corresponding source pixel and next succeeding source pixel are weighted by a fractional portion of the interpolation value. These two pixels are then added, yielding an interpolated destination pixel. Further, the first two source pixels are simultaneously weighted, and then the two succeeding source pixels are simultaneously weighted and added to the weighted two original source pixels. This yields two destination pixels using parallel processing. Two subsequent interpolation values are then chosen, and the process is repeated until an entire row of a source bit map is stretched. This can be repeated for all of the rows of a source bit map.

This parallel bit map stretching can be employed by a video or a graphic system in which a bit image is generated, and then a scale factor is determined, such as by window expansion by a user in a graphical interface. Based on this scale factor, the bit map is stretched, and then the stretched bit map is displayed on the screen.

A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:

FIG. 1 is a block diagram of a computer system having a processor and a multimedia extension unit of the present invention;

FIG. 2 shows a micro-architecture of the processor and the multimedia enhanced unit of FIG. 1.

FIG. 3 is a more detailed block diagram of the multimedia extension unit of FIG. 2,

FIG. 4 shows in more detail an operand router unit of FIG. 3;

FIG. 5 is a diagram illustrating the technique of pixel weighing to yield a stretched pixel map according to the invention;

FIG. 6 is a flowchart illustration of a routine for generating eight successive stretched pixels using parallel processing according to the invention;

FIGS. 7A-7B are diagrams illustrating parallel instruction flow used to set up initial interpolation values in the routine of FIG. 6;

FIG. 8 is a table illustrating the contents of certain registers at certain points in execution of the routine of FIG. 6,

FIG. 9 is a diagram illustrating the parallel instruction flow used to generate interpolation values in the routine of FIG. 6;

FIGS. 10A-10B are diagrams illustrating the parallel instruction flow and routing used to create weighted interpolated pixel values in the routine of FIG. 6;

FIG. 11 is a diagram illustrating the parallel instruction flow used to generate succeeding interpolation values for the routine of FIG. 6;

FIG. 12 is a block diagram illustrating the parallel instruction flow used to create two pixels based on four interpolated and weighted source pixels; and

FIG. 13 is a flowchart illustration of how the bit map stretching would be employed in a video system according to the invention.

Turning now to the drawings, FIG. 1 shows a block diagram of a computer 100. In FIG. 1, a central processing unit (CPU) 110 provides processing power for the computer system 100. The CPU 110 is preferably an Intel Pentium-Pro.RTM. processor with an multimedia extension unit (MEU), as shown in FIG. 2. However, a number of other microprocessors suitably equipped with an MEU may be used, including a PowerPC microprocessor, an R4000 microprocessor, a Sparc microprocessor, or an Alpha microprocessor, among others. The CPU 110 is connected to a read only memory (ROM) 112. The ROM 112 provides boot code such as a system BIOS software that boots up the CPU 110 and executes a power up self test (POST) on the computer system 100.

In addition, the CPU 110 is connected to a random access memory (RAM) 114. The RAM 114 allows the CPU 110 to buffer instructions as well as data in its buffer while the computer 100 is in operation. The RAM 114 is preferably a dynamic RAM array with 32 megabytes of memory. The CPU 110 is also connected to a real time clock and timer 116. The real time clock and timer 116 stores the dates and time information for the CPU 110. Furthermore, the real time clock and timer 116 has a lithium backup battery to maintain the time information even when the computer system 100 is turned off.

The CPU 110 is also connected to a disk storage device 118. The disk storage device 118 stores executable code as well as data to be provided to the CPU 110. Additionally, the CPU 110 is connected to a CD-ROM drive. Typically, an IBM PC compatible computer controls the disk drive 118 and the CD-ROM player 119 via an Intelligent Drive Electronics (IDE) interface.

Additionally, the CPU 110 is connected to a camera 120. The camera 120 supports video conferencing between the user and other users. The camera 120 essentially consists of a lens, a charge-coupled-device (CCD) array, and an analog to digital converter. The lens focuses light onto the CCD array, which generates voltages proportional to the light. The analog voltages generated by the CCD array are converted into a digital form by the analog to digital converter for processing by the CPU 110.

The CPU 110 is also connected to a video card 122. On the back of the video card 122 are one or more jacks. Connectors for monitors can be plugged into the jacks. The connectors, which are adapted to be plugged into the jacks of the video card 122, eventually are connected to the input of a monitor 124 for display.

A pen-based user interface is also provided. A digitizer 126 is connected to the CPU 110 and is adapted to capture user input. Additionally, a pen 128 is provided to allow the user to operate the computer. The pen 128 and digitizer 126 in combination supports another mode of data entry in addition to a keyboard 132.

While the video monitor 124 receives the output signals from the CPU 110 to the user, the keyboard 132 is connected to a keyboard controller 130 for providing input information to the CPU 110. Additionally, one or more serial input/output (I/O) ports 134 are provided in the computer system 100. Connected to the serial I/O ports 134 are a plurality of peripherals, including a mouse 140 and a facsimile modem 136. The facsimile modem 136 in turn is connected to a telephone unit 138 for connection to an Internet service provider 90, for example. Preferably, the modem 136 is a 28.8 kilobits per second modem (or greater) that converts information from the computer into analog signals transmitted by ordinary phone lines or plain old telephone service (POTS). Alternatively, the modem 136 could connect via an integrated service digital network (ISDN) line to transfer data at higher speeds.

Furthermore, a parallel input/output (I/O) port 142 is provided to link to other peripherals. Connected to the parallel I/O port 142 is a laser printer 144. Additionally, a microphone 148 is connected to a sound board 146 which eventually provides input to the CPU 110 for immediate processing or to a disk drive 118 for offline storage. The sound board 146 also drives a music quality speaker 150 to support the multimedia-based software. As multimedia programs use several medium, the multimedia computer system of the present invention integrates the hardware of the computer system 100 of the present invention. For example, the sound board 146 is used for sound, the monitor 124 is used to display movies and the CD-ROM player 119 is used for audio or video. In this manner, sounds, animations, and video clips are coordinated to make the computer session more friendly, usable and interesting.

Turning now to FIG. 2, a functional block diagram of the processor microarchitecture employed by the present invention is shown. The processor of the present invention is preferably based on an Intel-compatible Pentium-Pro microprocessor. The mode employed by the present invention is in addition to the existing modes of the 486 and Pentium processors, and unless otherwise indicated, the operation and features of the processors remain unchanged. Familiarity with the operation of the 486, Pentium and Pentium Pro are assumed in this description. For additional details, reference should be made to the appropriate data book. However, the invention could also be used in earlier processor generations such as the Intel Pentium.TM., 80486.TM., 80386.TM., 80286.TM., and 8086.TM. microprocessors. The use of the features of the multimedia extension unit could also be used with other types of microprocessors, including without limitation, the Power PC architecture, the Sparc architecture, and the MIPS R4000 architecture. For purposes of this disclosure, the terms microprocessor and processor can be used interchangeably.

In FIG. 2, the processor P employed by the present invention interacts with the system bus and the Level 2 cache (not shown) via a bus interface unit 300. The bus interface unit 300 accesses system memory through the external system bus. Preferably, the bus interface unit is a transaction oriented 64-bit bus such that each bus access handles a separate request and response operation. Thus, while the bus interface unit 300 is waiting for a response to one bus request, it can issue additional requests. The interaction with the Level 2 cache via the bus interface unit 300 is also transaction oriented. The bus interface unit 300 is connected to a combination instruction fetch unit and a Level 1 instruction cache 302. The instruction fetch unit of the combination unit 302 fetches a 32-byte cache line per clock from the instruction cache in the combination unit 302. The combination unit 302 is also connected to an instruction pointer unit and branch target buffer combination 304. The branch target buffer in turn receives exception/interrupt status and branch misprediction indications from an integer execution unit 324, as discussed below.

Additionally, the instruction fetch unit/L1cache combination 302 is connected to an instruction decoder 306. The instruction decoder 306 contains one or more simple decoders 308 and one or more complex decoders 310. Each of decoders 308 and 310 converts an instruction into one or more micro-operations ("micro-ops"). Micro-operations are primitive instructions that are executed by the processor's execution unit. Each of the micro-operations contains two logical sources and one logical destination per micro-operation.

The processor P has a plurality of general purpose internal registers which are used for actual computation, which can be either integer or floating point in nature. To allocate the internal registers, the queued micro-ops from the instruction decoder 306 are sent to a register alias table unit 312 where references to the logical register of the processor P are converted into internal physical register references. Subsequently, allocators in the register alias table unit 312 add status bits and flags to the micro-ops to prepare them for out of order execution and sends the resulting micro-ops to an instruction pool 314.

The instruction pool 314 is also connected to a reservation station 318. The reservation station 318 also receives the output of the register alias table 312. The reservation station 318 handles the scheduling and dispatching of micro-ops from the instruction pool 314. The reservation station 318 supports classic out-of-order execution where micro-ops are dispatched to the execution unit strictly according to data flow constraints and execution resource availability to optimize performance.

The reservation station 318 is in turn connected to a plurality of execution units, including a multimedia extension unit (MEU) 320, a floating point unit (FPU) 322, an integer unit (IU) 324, and a memory interface unit (MIU) 326. The MEU 320, FPU 322, IU 324 and MIU 326 are in turn connected to an internal data-results bus 330. The internal data-results bus 330 is also connected to the instruction pool 314, a Level 1 data cache 332 and a memory reorder buffer 334. Furthermore, the Level 1 data cache 332 and the memory reorder buffer 334 are connected to the bus interface unit 300 for receiving multiple memory requests via the transaction oriented bus interface unit 300. The memory reorder buffer 334 functions as a scheduling and dispatch station to track all memory requests and is able to reorder some requests to prevent data blockage and to improve throughput.

Turning now to the execution units, the memory interface unit 326 handles load and store micro-ops. Preferably, the memory interface unit 326 has two ports, allowing it to process the address on a data micro-op in parallel. In this manner, both a load and a store can be performed in one clock cycle. The integer unit 324 is an arithmetic logic unit (ALU) with an ability to detect branch mispredictions. The floating point execution units 322 are similar to those found in the Pentium processor. From an abstract architectural view, the FPU 322 is a coprocessor that operates in parallel with the integer unit 324. The FPU 322 receives its instruction from the same instruction decoder and sequencer as the integer unit 324 and shares the system bus with the integer unit 324. Other than these connections, the integer unit 324 and the floating point unit 322 operate independently and in parallel.

In the preferred embodiment, the FPU 322 data registers consist of eight 80-bit registers. Values are stored in these registers in the extended real format. The FPU 322 instructions treat the eight FPU 322 data registers as a register stack. All addressing of the data registers is relative to the register on top of the stack. The register number of the current top of stack register is stored in the top. Load operations decrement the top by one and load a value into the new top of stack register, and store operations store the value from the current top register in memory and then increment top by one. Thus, for the FPU 322, a load operation is equivalent to a push and a store operation is equivalent to a pop in the conventional stack.

Referring now to the multimedia extension unit (MEU) 320, the MEU 320 enhances the instruction set to include vector instructions, partitioned instructions operating on small data elements, saturating arithmetic, fixed binary point data, data scaling support, multimedia oriented ALU functions, and flexible operand routing. To preserve compatibility and minimize the hardware/software impact, the MBU 320 uses the same registers as the FPU 322. When new multimedia instructions are executed on the MEU 320, the registers of the FPU 322 are accessed in pairs. As the FPU 322 registers each have 80 bits of data, the pairing of the FPU 322 registers effectively creates four 160-bit wide registers, as further discussed below. Furthermore, the MEU 320 adds newly defined instructions which treat registers as vectors of small fixed point data values rather than large floating point numbers. Since the operating system saves the entire state of the FPU 322 as necessary during context switches, the operating system needs not be aware of the new functionality provided by the MEU 320 of the present invention. Although the disclosed system contemplates that the MEU 320 and the FPU 322 share logic or registers, the processor P could simply have snooping logic that maintains coherency between register values in completely separate MEU 320 and FPU 322 sections.

With respect to status and control bits, the FPU 322 has three registers for status and control: status word, control word, and tag word. These FPU 322 registers contain bits for exception flags, exception masks, condition codes, precision control, routing control and stack packs. The MEU 320 does not use or modify any of these bits except for the stack pack bits, which is modified because the MBU 320 result values are often not valid floating point numbers. Thus, anytime a MEU instruction is executed, the entire FPU tag word is set to 0xfffh, marking all FPU 322 registers as empty. In addition, the top of stack pointer in the FPU 322 status words (bits 11-13) is set to 0 to indicate an empty stack. Thus, any MEU 320 instruction effectively destroys any floating point values that may have been in the FPU 322. As the operating system saves and restores the complete FPU state for each task, the destruction of floating point values in the FPU 322 is not a problem between tasks. However, appropriate software action may need to be taken within a single task to prevent errors arising from modifications to the FPU 322 registers.

The sharing of the registers of the FPU 322 and the MEU 320 avoids adding any new software visible context, as the MEU 320 does not define any new processor status, control or condition code bits other than a global MEU extension enable bit. Furthermore, the MEU 320 can execute concurrently with existing instructions on the registers of the integer unit 324. Therefore, the CPU 110 logic is well utilized as the MEU 320 is efficiently dedicated to signal processing applications while the FPU 322 is dedicated to floating point intensive applications and the integer unit 324 handles addressing calculations and program flow control. Additionally, the MEU 320 allows for scalability and modularity, as the MEU 320 does not change the integer or load/store units. Thereby, the CPU 110 core design is not impacted when the MEU 320 is included or excluded from the processor P.

Referring now to FIG. 3, a more detailed block diagram of the MEU 320 is shown. The MEU 320 contains a vector arithmetic logic unit (VALU) 342. The VALU 342 is in turn connected to a plurality of vector registers 344, preferably four. These vector registers are preferably the same registers as those present in the FPU 322.

In the MEU 320, the FPU registers 344 are accessed in pairs. As each of the FPU 322 registers is 80 bits in width, the pairing of the FPU 322 registers effectively creates four 160-bit wide vector registers 344. Thus, as shown in FIG. 3, the register pairs of the FPU 322 are referred to as V0, V1, V2 and V3 and correspond to the physical FPU 332 registers. For instance, FPU 322 physical register 0 is the same as the lower half of the MEU 320 vector register V0. Similarly, FPU 322 physical register 1 is the same as the upper half of MBU 320 vector register V0, while the FPU 322 physical register 7 is register V3. Furthermore the MEU 320 vector register V3. Furthermore, in the MEU 320 of FIG. 3, the stack based access model of the 80.times.87 floating point instructions is not utilized. Instead, the 160-bit registers V0-V3 are partitioned to form vectors of 10-bit or 20-bit data elements.

The output of the vector registers 344 are subsequently provided to an operand router unit (ORU) 346 and the VALU 342. Each vector instruction controls both the ORU 346 and the VALU 342. In combination, the ORU 346 and the VALU 342 allows the processor P to simultaneously execute software using flexible operand routing and multiple operation. Referring to the flow graph of FIG. 15, for example, the VALU 342 operates on the nodes and the ORU 346 implements diagonal interconnections. Thus, because vector arithmetic of different types and data movement can be processed in groups simultaneously, the VALU 342 and the ORU 346 provide high performance.

The VALU 342 can perform a variety of operations, including addition, subtraction, multiply, multiply/accumulate, shifting and logical functions. The VALU 342 assumes that each of the 160-bit registers 344 is partitioned into 10-bit or 20-bit source operands and destinations. Thus, the VALU 342 can execute 8 or 16 individual operations per instruction. A three-operand instruction format is supported by the VALU 342: source A, source B, and destination registers for each instruction. Additionally, certain operations, such as multiply/accumulate use the destination as an implied third source operand.

The MEU 320 operates primarily in fixed point operation. The difference between fixed point and integer data is the location of the binary point. In the MEU 320, the binary point is assumed to be to the left of the most significant bit. Numbers in the MEU 320 can be considered as fractions that nominally occupy the range from plus 1 to minus 1. The advantage of this format over the integer format is that the numerical magnitude of the data does not grow with each multiply operation as the product of two numbers in the plus 1 to minus 1 ranges yields another number in the plus 1 to the minus 1 range. Therefore, it is less likely the data will need to be rescaled.

The MEU 320 takes advantage of the full 80-bit width of the FPU 322 register set. The MEU 320 loads data from memory in 8-bit or 16-bit quantities, but the data is expanded to 10 bits or 20 bits as it is placed into the vector registers 344 (V0 . . . V3). The extended provision provides two benefits: (1) simplifying support for signed and unsigned data, and (2) helping to avoid overflow conditions and round-off errors on intermediate results.

Furthermore, the VALU 342 performs all arithmetic operations using saturating arithmetic. Saturating arithmetic differs from the more familiar modular arithmetic when overflows occur. In modular arithmetic, a positive value that is too large to fit into destination wraps around and becomes very small in value. However, in saturating arithmetic, the maximum representable positive value is substituted for the oversized positive value. This operation is often called clipping.

Additionally, the VALU 342 performs adds, subtracts and Boolean operations on 10-bit to 20-bit quantities. If the result of an add or subtract is outside of the representable range, the result is clipped to the largest positive or negative representable value. However, Boolean operations are not clipped. Furthermore, the result of the add, subtract, and move operations may optionally be shifted right by one bit before being stored to the destination. This scaling can be used to compensate for the tendency of data magnitude to grow with each add or subtract operation. Multiply operations take two 10-bit or 20-bit signed factors and generate a 19-bit or 39-bit signed product. The least significant 9 or 19 bits of the product are rounded and dropped before stored into the 10-bit or 20-bit destination register. As simple multiply operations typically do not overflow, they do not need to be clipped. However, multiply/accumulate operations do require clipping.

Turning now to FIG. 4, the details of the operand routing unit 346 are shown. The ORU 346 allows operands to be flexibly moved within and between large 160-bit registers. As vector processors generally must load data from memory in large monolithic chunks, the ability to route operands is useful for the MEU 320. The ability to flexibly access and route individual operands, the ORU 346 provides the ability to "swizzle" the data partitions in a vector register as data moves through it. The swizzling operation allows the operands to be shuffled as needed by the application concurrently with the execution of the vector ALU operations. Thus, a smaller amount of data is required to yield useful results. Thus, the load and store units are less likely to be overloaded, leaving greater bandwidth for the integer, non-vector units to perform work.

As shown in FIG. 4, the ORU 346 is essentially an enhanced 8.times.8 crossbar switch which works with a plurality of slots. In the preferred embodiment, eight slots are provided for each of a source B register 350, source A register 354 and a destination register 358. The source B register 350 is connected to a multiplexer 352. The output of the multiplexer 352 and the source A register 354 is provided to a VALU partition 356. The VALU partition 356 in turn is connected to the destination register 358.

In the vector source B register 350, each slot contains either one 20-bit partition or two 10-bit partitions, depending on the partition width as specified in the vector instruction. For 10-bit partitions, the MEU 320 simultaneously performs independent but identical operations on the two partitions in a slot. Furthermore, each slot in the destination register 358 can independently receive one of eleven values: the value in one of the eight source slots 350 and 354, a Z value (0), a P value (1) or an N value (-1). During the execution of codes by the MEU 320, all vector instructions use a single opcode format that simultaneously controls the VALU 342 and the ORU 346. This format is approximately eight bytes long. Each instruction encodes the two source registers, the destination register, the partition size, and the operations to be performed on each partition. In addition, each instruction encodes the ORU 346 routing settings for each of the eight slots. Normally, any two of the vector operations defined in the following table may be specified in a single vector instruction. Each slot can be arbitrarily assigned either of the two operations. The vector instructions offered by the MEU 320 is shown in Tables 1 and 2, as follows:

Turning now to load and store instructions, each type of operation has two versions: one that moves 16 bytes of memory and one that moves 8 bytes of memory. The 8-bytes versions are defined because this is often the amount of data needed; loading or storing 16 bytes in these cases would be wasteful. Further, the 8-byte loads and stores can be used to convert between byte-precision data and word-precision data. The 16-byte loads and stores operate on the entire 160-bit vector register. The 8-byte stores for 20-bit partitions store only the values from slots 4 through 7. The 8-byte stores for 10-bit partitions store only the upper half of each of the eight slots. The 8-byte loads for 20-bit partitions load the memory data to slots 4 through 7; slots 0 through 3 are set to zero. The 8-byte loads for 10-bit partitions load the memory data to the upper half of each slot; the lower half of each slot is set to zero. Even though 8-byte loads only copy memory to half of the bits in a vector register, the entire 160-bit vector register is updated by padding the unused partitions with zeros. This feature greatly simplifies the implementation of register renaming for the MEU because partial register updates do not occur. Table 3 illustrates the load and store instructions in more detail:

The mnemonics for the vector instruction need to specify the operations to perform on each partition as well as the sources, destination and ORU routing. This is notated as follows:

This instruction performs adds and reverse subtracts. V3 is the destination; V2 is sourceA; V1 is sourceB. The slots for the operand specifier and the routing specifier are laid out in decreasing order from left to right.; slot 7 and 6 get sbr, slot 5 gets add, and so forth. The "word" symbol specifies that the instruction works on a 20-bit partitions. The routing specifier for sourceB is set for the following (the number after the points specify slot numbers):

dest.7 .rarw.=--sourceA.7+sourceB.3

dest.6 .rarw.=--sourceA.6+sourceB.7

dest.5 .rarw.=sourceA.5+#1.0

dest.4 .rarw.=sourceA.4+sourceB.3

dest.3 .rarw.=--sourceA.3+#0.0

dest.2 .rarw.=sourceA.2+sourceB.1

dest.1 .rarw.=--sourceA.1+#-1.0

dest.0 .rarw.=sourceA.0+sourceB.2

Turning to FIG. 5, a graphical representation of the operation of the stretch bit algorithm according to the invention is shown. Illustrated are a series of source pixels represented by P.sub.0 . . . P.sub.4. These are to be mapped to destination pixels P.sub.0 ' . . . P.sub.4 '. In the illustration of FIG. 5, it is assumed that the scale factor is 1.25 times; that is, the resulting image is to be 125 percent of the size of the original image.

Given a bit mapped image with pixels P.sub.0 . . . P.sub.4, it is necessary to interpolate between source pixels to calculate the value of a particular destination pixel. In the discussion that follows, it is assumed that the pixels are 32 bit pixels with three color values plus alpha that can be interpolated through weighing and addition.

To perform the stretching according to the invention, first the reciprocal of the stretch factor is taken; here, 0.8 is the reciprocal of 1.25. Then, a series of interpolation values are calculated, with each successive interpolation value being the value of the previous interpolation value plus the reciprocal of the stretch factor. This is illustrated by a series of interpolation values 400, which each have both integer and fractional portions. The integer parts are denoted I.sub.n, while the corresponding fractional parts are denoted i.sub.n. The first interpolation value is 0.0, the next is 0.8, the next is 1.6, etc.

To calculate each destination pixel, the integer portion of the interpolation value I.sub.n, is used to determine the first source pixel, while the fractional portion i.sub.n is used to determine a weighing factor between the first source pixel and its next succeeding source pixel. This is illustrated by a series of equations 402, 404, and 406. Referring first to equation 402, the value of the pixel P.sub.0 ' is calculated. First, the source pixel P.sub.n is chosen according to the value of I.sub.1. Here, the initial interpolation value I.sub.1 is zero, so this indicates that the first destination pixel is to be generated from the weighted average of P.sub.0 and the next pixel, P.sub.1. P.sub.0 (that is, P.sub.I1) is first multiplied by 1-i.sub.1. In this case, i.sub.1, is zero, indicating that the weighing is to be totally towards the first pixel. This results in P.sub.0 ' being set equal to the value of P.sub.0, with no weighing of P.sub.1 being added.

Turning to equation 404, the interpolation value for the second destination pixel P.sub.1 ' is found in I.sub.2 and i.sub.2 I.sub.2 is zero, indicating again that the weighing is to be determined between pixel P.sub.0 and P.sub.1. The weighing factor i.sub.2, is 0.8, indicating that the pixel P'.sub.1 should be the weighted combination of 0.8(P.sub.1)+0.2(P.sub.0).

Equation 406 illustrates the next interpolation between initial pixels P.sub.1 and P.sub.2, yielding a pixel P'.sub.2. In equation 406, the integral portion I.sub.3 of the interpolation value is one, indicating P.sub.1, rather than P.sub.0, is the first pixel, while P.sub.2 is the second pixel between which the value of P'.sub.2 should be interpolated. The fractional portion i.sub.3 is 0.6, indicating 0.6 (P.sub.2)+0.4 (P.sub.1) will yield the weighted interpolation of pixel P.sub.2 '. Turning to FIG. 6, a flowchart is shown illustrating a STRBLT routine 420 for implementation on the multimedia extension unit 320 for parallel determination of new pixels relative to source pixels in a stretch blt algorithm. Of note, this routine only stretches in the horizontal direction (the more difficult direction). To stretch in the vertical direction, a similar technique is provided, but the interpolations are between entire rows of pixels rather than two adjacent pixels. As an overview, a routine STRBLT 420 calculates two 32-bit destination pixels at a time by loading two source pixels for each of the destination pixel and "weighing" the source pixels by their respective fractional portion of the interpolation values, and then adding the weighted values. The interpolation values are determined by taking the reciprocal of the stretch factor. In the attached source code appendix, a stretch factor of 1.455 is assumed. The reciprocal results in an interpolation value of 0.687, with each destination pixel P' having a corresponding interpolation value. The first interpolation value is zero, the second is the reciprocal of the stretch factor, the third is two times the reciprocal of the stretch factor, etc. The routine 420 first establishes eight interpolation values, calculates the first eight destination pixels, and generates the next eight interpolation values by adding 8 times the reciprocal of the stretch factor to each of the original eight values. The reciprocal of the stretch factor is labeled the ".DELTA.d" value. At some point, the integer portion of the interpolation values will overflow, so they would have to be scaled down by subtracting out an integral amount. Although not illustrated, this step will be understood by one of ordinary skill in the art.

The STRBLT routine 420 begins at step 422, where vector registers V1 and V3 are set up. This is performed by a series of instructions 500-508, illustrated in FIGS. 7A-7B. At the end of this series of instructions, V1 contains eight interpolation values, designated as a vector V.sub.-- INTERP ›7 . . . 0!. These values progress from zero to 7.DELTA.d inncrements of .DELTA.d. V3 is set up principally with 8.DELTA.d V3.2 (slot 2 of V3). 8.DELTA.d is an interpolation multiplier INTERP.sub.-- MULT, which is added to each of the interpolation values in V.sub.-- INTERP›7 . . . 0! after each 8 new pixels have been calculated.

Proceeding to step 424, the interpolation vector V.sub.-- INTERP›7 . . . 0! is stored to memory, and the first two fractional interpolation values are loaded in V1. That is, the fractional portions of i.sub.1 and i.sub.2 are loaded into V1 from the interpolation values stored to memory. This is further discussed below in conjunction with FIG. 8. Proceeding to step 426, the top four slots of V3 are loaded with the appropriate interpolation multipliers. The interpolation values were previously loaded into the high order portion of V1 in step 424. These are then manipulated to yield the appropriate weighing multipliers for each first and subsequent source pixels that correspond to each of the two destination pixels being generated on this pass. This is further discussed below in conjunction with FIG. 9.

Proceeding to step 428, the two sets of first and subsequent source pixels for destination pixels are loaded based on the integer portion of the interpolation value. This corresponds to four source pixels, two for each destination pixel. Proceeding to step 430, the weight of the two subsequent source pixels are calculated, and then at step 432, the weight of the first two source pixels are calculated and summed with the weight of the two subsequent source pixels. The resulting two destination pixels are then stored at step 436. This is all further discussed below in conjunction with FIGS. 10A-10B.

Proceeding to step 438, the sequence of 424-436 is repeated for the next six interpolation values. The difference in the subsequent loops is principally that the different fractional and integral portions of the interpolation values are used for each subsequent two pixels. That is, the second two pixels are calculated based on I.sub.4, i.sub.4, I.sub.3, and i.sub.3, the next two based on I.sub.6, i.sub.6, I.sub.5, i.sub.5, and the last two pixels are calculated based on I.sub.8, i.sub.8, I.sub.7, i.sub.7.

At step 440, it is determined whether more destination pixels must be calculated for a row. If so, control proceeds to step 442, where the next interpolation values are set up by adding INTERP.sub.-- MULT (that is 8.times..DELTA.d) to each of the interpolation values in the interpolation vector V.sub.-- INTERP›7 . . . 0!. If at step 440 all of the pixels in the present row have been calculated, control proceeds to step 444, where it is determined whether more rows remain to be stretched. If so, the pointer is set to the start of the next row, and control loops to step 422, where V1 and V3 are again set up to their initial interpolation values. If more rows do not remain at step 444, the routine returns at step 446. Alternatively, before step 446, the rows can be vertically stretched as well by interpolating between rows.

Turning to FIGS. 7A and 7B, the parallel instructions for setting up the vector registers V1 and V3 are graphically illustrated. These instructions are performed at step 422 of FIG. 6. As is earlier described, the multimedia extension unit 320 includes vectors that contain 20 bits of internal precision per slot, which corresponds to 16 bits per slot of external storage. This can be accessed in a word format, or in two split 10 bit half-word formats in which a byte of 8 bits is written to or read from each slot. According to the invention, the integer portion of each interpolation value is aligned with the upper half of the slot, while the fractional portion is aligned with the lower half of the slot. This leads to greater efficiency and simplicity in the execution of the routine.

As a first step, a delta.sub.-- d value is calculated to be one over the stretch factor, or the scale. This is illustrated in FIG. 7A, in which vector slot V3.2 contains delta.sub.-- d, the unscaled reciprocal of the stretch factor. This is arithmetically shifted right in instruction 500 by four bits, and then arithmetically shifted right by three bits in step 502, yielding a scaled, or normalized, reciprocal stretch factor .DELTA.d. This is contained in V3.2, step 502, and turning to FIG. 7B, is used in instruction 504 where .DELTA.d from vector slot V3.2 is simultaneously loaded into the top seven slots of vector V1. This results in .DELTA.d being in the top seven slots of V1, with a zero value being contained in slot V1.0. A series of instructions 506 are then performed that create the interpolation of vector V.sub.-- INTERP›7 . . . 0!. Specifically, the six high order slots of V1 have added to them the scaler .DELTA.d from V3.2, yielding 2.DELTA.d in each of the six high order slots. Then, the five high order slots of V1 are added to .DELTA.d, yielding 3.DELTA.d, etc., until at the end of the sequence of instructions 506, V1 contains a series of successive integral multiples of .DELTA.d. Because of appropriate scaling, the integral portion of .DELTA.d is contained in the high order half of V1, while the fractional portion is contained in the low order half.

After V3.2 has been used for addition to V1 to create V.sub.-- INTERP›7 . . . 0!, V1.7, or V.sub.-- INTERP›7! is added to V3.2 at instruction 508, yielding the interpolation multiplier INTERP.sub.-- MULT, which equals 8.DELTA.d. As discussed previously, this will ultimately be added to each of the slots of V1 yielding the next series of interpolation values.

Turning to FIG. 8, as discussed above, the integral and fractional portions of each interpolation value are stored in a 20-bit slot, with a 10-bit high order portion containing the integral value and the adjacent 10-bit low portion containing a fractional portion. This is illustrated in FIG. 8, where the contents of the vector V1 are illustrated at times 509 and 510. At time 509, V1 contains the first eight interpolation values in its 20-bit slots, with an integral integer portion I.sub.n adjacent to each fractional portion i.sub.n. This is then stored to memory, and then read from memory using a byte load instruction yielding the vector V1 at time 510. The low order portion of each slot of V1 then contains zero, while the high order portions contains i.sub.1, I.sub.1, i.sub.2, I.sub.2, etc. These interpolation values are then used to generate the first two scale factors through a series of instructions 512 illustrated in FIG. 9. The instructions 512 first route the fractional portion i.sub.1 of the first interpolation value to the fourth and fifth slots of V3 and the fractional portion i.sub.2 to the sixth and seventh slots of V3. Then, the fourth and sixth slots are subtracted from one, yielding the upper four slots of V3 containing {i.sub.2, 1-i.sub.2, i.sub.1, 1-i.sub.1 }. The fourth and fifth slots contain the weighing factors that will yield the first destination pixel to be calculated, while the sixth and seventh slots contain the weighing factors to yield the second destination pixel.

Then, with the appropriate weighing factors calculated, the pixels with which the weighing factors must be multiplied are loaded. These are the pixels illustrated in FIG. 5. Turning back to FIG. 8, illustrated are the vectors V0 and V2 at a time 514. The upper portion of the four least significant slots of V0 have been loaded with the 32-bit pixel P.sub.I1. That is, the integral value I.sub.1 is used to map to the first pixel that will be used for interpolation. The upper four slots are loaded with P.sub.I1+1, which is the next adjacent pixel to the first integral pixel P.sub.I1. Similarly, V2 is loaded with P.sub.I2 and P.sub.I2+1.

The pixels stored in V0 will then be weighted with i.sub.1 and 1-i.sub.1 as held in V3, and the pixels held in V2 will be weighted with i.sub.2 and 1-i.sub.2. This is achieved by instructions illustrated in FIGS. 10A and 10B. First, P.sub.I1+1 and P.sub.I2+1 are routed from V0 and V2 into V1 in an instruction 516. The upper four slots of V1 then contain P.sub.I2+1, while the lower four slots contain P.sub.I1+1. These pixels must then be weighted by the interpolation values i.sub.2 and i.sub.l. This is accomplished in step 518, yielding V1 containing P.sub.I2+1 .multidot.i.sub.2 and P.sub.I1+1 .multidot.i.sub.1. Referring back to FIG. 5, it is understood in reference to the calculation of P'.sub.0 and P'.sub.1, that this is half of the calculation necessary to yield those two destination pixels. Referring to FIG. 10B, P.sub.I2 and P.sub.I1 are routed from V0 and V2 into V0, yielding P.sub.I2 in the top four slots and P.sub.I1 in the bottom four slots. These two pixels are then simultaneously weighted and added to their previously weighted successive pixels P.sub.I2+1 and P.sub.I1+1 by a multiply and accumulate instruction illustrated as 522. Then, 1-i.sub.2, found in V3.6, is multiplied by P.sub.I2, and 1-i.sub.1, located in V3.4, is multiplied by P.sub.I1. These values are then added to i.sub.2 P.sub.I2+1 and i.sub.1 P.sub.I1+1 to yield:

P'.sub.1 =P.sub.I2+1 (i.sub.2)+P.sub.I2 (1-i.sub.2)

and

P'.sub.0 =P.sub.I1+1 (i.sub.1)+P.sub.I1 (1-i.sub.1)

Thus, using operand routing and selectable operations per slot, two 32-bit destination pixel values have been simultaneously generated based on four source pixel values and two interpolation values. These values are then stored, as previously discussed, in conjunction with step 436.

It will be appreciated that the next six pixels are calculated by similar instructions illustrated in FIGS. 8-10B. These instructions are designed as instructions 524, 526, and 528 in the source code appendix. For the next two pixels, rather than i.sub.1 and i.sub.2 being routed by instructions 512 in FIG. 9 and P.sub.I1 and P.sub.I2 being loaded in step 514 in FIG. 8, i.sub.3 and i.sub.4, and the corresponding pixels P.sub.I3 and P.sub.I4 are loaded along with the succeeding pixels P.sub.I3+1 and P.sub.I4+1. For the final four values, effectively the same sequence is repeated, but in contrast to at time 510, V1 in its high order slots contains I.sub.8,i.sub.8 . . . I.sub.5,i.sub.5. After all eight values have been generated, at step 442 the next interpolation values are generated.

Turning to FIG. 11, shown is the parallel instruction executed to set up the next interpolation values in step 442. Instruction 530 adds the scaler INTERP.sub.-- MULT, which is equal to 8.DELTA.d, to each slot of the vector V.sub.-- INTERP›7 . . . 0!, held in vector register V1. This results in each interpolation value being incremented by 8.DELTA.d, yielding the next eight interpolation values.

Finally, turning to FIG. 12, shown is a diagram illustrating the parallel generation of two interpolated 32-bit pixels according to the invention. As discussed above in conjunction with FIGS. 5-11, a step 600 shows two pixels P.sub.I1 and P.sub.I2 being simultaneously loaded. Then at step 602 these pixels are simultaneously weighted with 1-i.sub.1 and 1-i.sub.2. Then, at step 604, the next successive two pixels P.sub.I1+1 and P.sub.I2+1 are simultaneously loaded, and then weighted by i.sub.1 and i.sub.2 at step 606. Simultaneously, however, these weighted successive pixels are added to the original weighted pixels P.sub.I1 and P.sub.I2, yielding P'.sub.0 and P'.sub.l. That is, step 606 takes place in forming a multiply and accumulate instruction. Thus, using the operand routing and selectable operations per slot in a multimedia extension unit 132, yields a highly efficient method of performing a stretch of a pixel map.

Turning to FIG. 13, shown is a flowchart illustration of how the bit map stretching could be employed according to the invention. Beginning at step 700, the routine of FIG. 13 proceeds to step 702, where a source bit map is generated. Then, proceeding to step 704, a scale factor is selected. This could be performed, for example, in response to a user resizing a window in a graphical operating system. The scale factor could even be different in the horizontal and vertical directions. Proceeding to step 706, the bit map is stretched based on the scale factor provided in step 704. This is performed by executing the STRBLT routine 420, or some similar routine, dependent on the format of the bit map. Proceeding to step 708, the stretch bit map is displayed on the video screen. The routine then ends at step 710. This routine 700, or the STRBLT routine 420, would preferrably be stored either as part of the operating system on hard disk or other readable media, or as part of an embedded read only memory toolbox.

The foregoing disclosure and description of the invention are illustrative and explanatory thereof, and various changes in the size, shape, materials, components, circuit elements, wiring connections and contacts, as well as in the details of the illustrated circuitry and construction and method of operation may be made without departing from the spirit of the invention. ##SPC1##