United States Patent [191
`Celi, Jr. et a].
`
`‘
`
`US005742797A ‘
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,742,797
`Apr. 21, 1998
`
`[54]
`
`DYNAMIC OFF-SCREEN DISPLAY MEMORY
`MANAGER
`
`5,592.670
`5,606.657
`
`1/1997 Fletcher ................................ .. 395/670
`2/1997 Dennison et a1. .................... .. 395/501
`
`[75]
`
`Inventors: Joseph Celi, J r.. Boynton Beach;
`Roger Louie. Deer?eld Beach;
`Jonathan Mark Wagner. Coral
`Springs. all of Fla.
`
`[73]
`
`Assignee: International Business Machines
`Corporation. Armonk. N.Y.
`
`[21]
`[22]
`[5 1]
`[52]
`[5 8]
`
`[56]
`
`Appl. No.: 513,710
`Filed:
`Aug. 11, 1995
`
`1m. (:1.6 ..
`
`................. .. G06T l/60
`
`.. 395/507; 395/497.01
`US. Cl. ............ ..
`Field of Search ................................... .. 345/185. 189.
`345/200. 201. 203', 395/507. 497.01. 497.02.
`509. 520. 492. 497.04. 497.03
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,742,474
`
`5/1988 Knierim ................................ .. 345/187
`
`3/1990 Furlong . . . . .
`4,906,985
`l/1991 Cam'ck ........ ..
`4,983,958
`1/1992 Nomura eta]
`5,083,121
`7/1992 Yurt et al
`5,132,992
`5,206,859 4/1993 Anzai .......... ..
`5,291,188
`3/1994 McIntyre et al
`5,309,173
`5/1994 Izzi eta]. ........ ..
`5,319,395
`6/1994 Larky eta]
`5,335,322
`8/1994 Mattialo ...... ..
`5,361,387 11/1994 Millal' et a1. ........ ..
`5,392,415
`2/1995 Badovinatz et al.
`5,408,650
`4/1995 Arsenault ........ ..
`
`. . . . . .. 345/189
`345/190
`345/200
`375/240
`370/522
`345/189
`345/190
`345/190
`395/511
`395/511
`395/406
`395/704
`
`OTHER PUBLICATIONS
`
`IBM Technical Disclosure Bulletin “Linked List Search
`Table Array for Free Storage Blocks” v01. 33 No. 8 pp.
`474-479. Jan. 1991.
`S.L. Goncharsky et a1. “Use of Binary Trees for Storage
`Allocation” IBM Technical Disclosure Bulletin vol. 24 No.
`6 pp. 2710-2711. Nov. 1981.
`SL. Goncharsky et al. Use of Binary Trees for Storage
`De-allocation IBM Technical Disclosure Bulletin vol. 24
`No. 6 p. 2713. Nov. 1981.
`
`Primary Examiner-Kee M. Tung
`Attorney Agent, or Firm—Mark S. Walker; Andrew J.
`Dillon
`
`ABSTRACT
`
`[57]
`A display memory manager allocates and deallocates 05
`screen video memory by dividing the memory space into a
`plurality of lapping and non-overlapping regions each
`capable of storing a different amount of digitized display
`data. and creating a linked list data structure indicative of the
`allocated and unallocated regions and various combinations
`of the unallocated regions. Upon receiving a request for
`oif-screen display memory the display memory manager
`traverses the linked list data structure searching for a region.
`or combination of regions. large enough to store the
`requested amount of digitized display data. Once a region or
`combination of regions has been found and allocated. the
`linked list data structure is updated to indicate that the new
`regions are now allocated and hence unavailable to a sub
`sequent requested allocation unless dez?located.
`
`5,414,826
`5/1995 Garcia . . . . . . .
`. . . . . .. 395/428
`5,561,786 10/1996 Morse .............................. .. 395/49701
`
`21 Claims, 7 Drawing Sheets
`
`201B
`
`205
`
`APPUCATION
`PROGRAMS
`
`Q
`L 201A
`
`204
`
`DEVICE
`HELPERS
`
`DEVICE DRIVER _ /_ 203A
`OFF-SCREEN- ‘
`olsmmgzégonv
`
`SOFTWARE
`
`203
`
`‘
`
`‘
`
`' rqglzn? * ‘
`
`217
`
`'
`
`-
`
`GRAPHIC /1--[\ OFF
`NE
`SCREEN
`ENGI
`VRAM
`’
`
`5L;
`
`HARDWARE
`
`/-21"3
`FRAME BUFFER ‘/
`
`I
`
`2110 —/
`
`2110
`
`/
`
`211A
`
`Apple Inc. v. Parthenon
`Ex. 1010 / Page 1 of 16
`
`

`
`U.S. Patent
`
`la2LD..A
`
`8991
`
`Sheet 1 of 7
`
`<m:<2:”0
`eI
`
`
`
`«flmm:moo.
`
`mo:
`
`
`
`m>EozmaDMXImama20m00m>_momFExm_o
`
`
`
`
`
`8.
`
`o2I\
`
`mmjoyfizoo
`
`
`
`xwammjompzoummjompzooE25.
`
`m5.0..
`
`m
`
`0:.
`
`«Ssm:m>m
`
`m:
`
`O_QD<
`
`2m»m>mm:w
`
`w:n__._.—.
`
`<_._._.
`
`
`
`8.v_mo>>Ez
`
`E:m8T\<I|I
`
`
`
`Rm?Korma:~.b~r.w
`
`zmozfimz
`mm_E<o<mm
`
`5.5zoazfixm
`mmjomfizoo
`
`mmjomezoo
`
`89><55
`
`
`
`02¢.om<om>mx
`
`mmsoz
`
`mmjompzoo
`
`>mo_2m_2
`
`mm._._oEzoo
`
`mam
`
`mmjompzoo
`
`E:mmmpz_
`
`mmjomhzoo
`
`Ex. 1010 / Page 2 of 16
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 2 of 7
`
`5,742,797
`
`& zwwmowdmo
`
`\I Now
`
`vow
`
`‘low
`
`mom
`
`mrow
`
`Ex. 1010 / Page 3 of 16
`
`

`
`U.S. Patent
`
`899112rPA
`9
`
`Sheet 3 of 7
`
`5,742,797
`
`oz_m<mmoz_
`
`mum>mo_2m_s_
`
`
`
`
`
`
`
`
`
`.mu.mu.ilmumooo.:<zo_»<oo._mum~.oo._._<20:59mumnoO._._<zo_+<oo._>E.zm_
`
`
`
`mummoO._._<ZO_h<OO._
`
`>>%
`
`Ex. 1010 / Page 4 of 16
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 4 of 7
`
`5,742,797
`
`Qv .Ubw
`
`5:604:23
`
`T1: N3
`
`a“ was; Tl Ev
`
`g. ww<s=
`
`..||l Nov
`
`Q5 <2
`0 ‘II 5v
`
`$209223!‘ 0;
`
`$20922:
`$50322:
`
`TI #3
`
`TI. 3".
`
`DEN DIN
`\ \ NOR
`
`Ex. 1010 / Page 5 of 16
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 5 of 7
`
`5,742,797
`
`(
`
`START
`
`I
`
`f 500
`
`INITIALIZE "POINTER“ TO THE
`FIRST ELEMENT OF THE
`LINKED LIST
`
`READ THE REQUESTED
`MEMORY AMOUNT
`
`501
`
`s02
`
`j’ 506
`_
`INCREMENT
`POINTER To THE
`NEXT ELEMENT IN
`THE LINKED LIST
`
`IS THE REQUESTED MEMORY
`AMOUNT GREATER THAN THE SIZE OF
`THE REGION ASSOCIATED WITH THE
`URRENT LINKED LIST ELEMENT’7
`
`IS THE REGION
`ALLOCATED?
`
`508A
`
`FIG. 5A
`
`Ex. 1010 / Page 6 of 16
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet
`6 0f 7
`
`5,742,797
`
`088
`5
`
`ASSIGN IMAGE TO THE
`CURRENT REGION
`
`/- 509
`
`CHANGE STATUS OF THE
`REGION'S "ALLOC" FLAG TO
`ALLOCATED
`
`[51o
`
`RECOMPUTE THE AVAILABLE
`MEMORY REGION OPTIONQ
`AND REFORM THE LINKED
`LIST
`
`/512
`
`FINISH
`
`FIG. 5B
`
`Ex. 1010 / Page 7 of 16
`
`

`
`US. Patent
`
`Apr. 21, 1998
`
`Sheet 7 0f 7
`
`5,742,797
`
`I
`
`~*~
`
`START \I
`
`__. _/
`
`600
`
`f
`
`CHANGE STATUS OF THE
`STATUS FLAG OF THE REGION
`TO BE DEALLOCATED TO
`UNALLOCATED
`
`I
`
`RECOMPUTE THE AVAILABLE
`MEMORY REGION OPTIONS AND
`REFORM THE LINKED LIST
`
`602
`
`604
`
`I
`
`FINISH
`
`I
`
`FIG. 6
`
`Ex. 1010 / Page 8 of 16
`
`

`
`5.742.797
`
`1
`DYNAMIC OFF-SCREEN DISPLAY MEMORY
`MANAGER
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`This application contains subject matter related to a
`co-pending. commonly assigned U.S. patent application
`designated Ser. No. TBD. ?led even date herewith. entitled
`“Method and Apparatus for Virtualizing Off-Screen Memory
`of a Graphics Engine”.
`
`TECHNICAL FIELD
`
`The present invention is directed to a memory manage
`ment system. and more particularly to a display memory
`management system for dynamically allocating and deallo
`cating regions of off-screen display memory in a multi
`media personal computer system.
`
`10
`
`15
`
`2
`controller 105 connects to the bus 108 for controlling a
`keyboard input device 105A and a mouse input device 105B.
`A DMA controller 107 is provided for performing direct
`memory access to system RAM 106. The computer also
`includes a video controller 111 which controls the display of
`information on a display 111A (e.g.. a CRT or ?at screen).
`The display 111A. under the control of the computer system
`100. generates a two dimensional array of picture elements
`(“pixels”). which may be independently controlled to form
`an image. Other input and output devices. such as an audio
`subsystem 116. may be connected to the system through an
`expansion slot 115.
`The computer 100 is generally controlled and coordinated
`by operating system software. OS/2® is an exemplary
`operating system. which is developed and sold by the
`International Business Machines Corporation (“IBM”).
`Boca Raton. Fla.. the assignee of the present invention.
`Conventional operating systems control and schedule com
`puter processes for execution. perform memory
`management. provide ?le system services. provide network
`ing and I/O services. and provide a user interface. such as a
`graphical user interface (“GUI”). User applications
`programs. such as text editors and spreadsheets. directly or
`indirectly. rely on these and other operating system capa
`bilities to properly use the computer system.
`In recent years with the development of graphical user
`interfaces and their widespread acceptance. the display of
`information to a user has become relatively sophisticated
`and computationally demanding. Modern computers use
`“graphics" capabilities to produce various graphical items.
`such as lines. boxes. and circles. on the display 111A.
`possibly in color. These graphics capabilities may be used.
`for example. to display information within a “window”
`displayed on the display 111A using a GUI (e.g.. the
`Presentation ManagerTM GUI which runs with the 08/2
`operating system).
`In addition to graphics. modern computers are increas
`ingly using multimedia techniques. which store. organize.
`and display various forms of data. including textual data.
`digital audio data. digital video data. and digital musical
`data. For example. a computer using multimedia techniques
`may play back video data and audio data to produce a movie
`clip video sequence on the display 111A with synchronized
`audio output from the audio subsystem 116.
`Graphical displays and video images are conventionally
`produced by storing data for each pixel of the display 111A
`in a corresponding location of a “frame bulfer” 11113. A
`typical frame buffer 111B is constructed in a well known
`manner from special memory chips called video random
`access memory Orereinafter “VRAM”). which allows con
`ventional read and write operations to be performed to
`memory cells of the VRAM on one port. while allowing data
`to be scanned out from the cells via a second. scan port. The
`display controller 111 typically scans the data out and uses
`it to cause corresponding pixels of the display 111A to be
`energized in accordance with the display data.
`The display data may indicate whether or not a pixel
`should be illuminated. or if color images are involved. may
`indicate the desired luminance and chrominance for a pixel.
`Moreover. color data may be implemented according to a
`variety of well known formats. such as YUV. RGB. RBG.
`etc.. which require many bits of data per pixel. Modern color
`formats. for example. may require up to three bytes. or
`twenty four bits. of information per pixel.
`Producing graphical and video images requires a substan
`tial amount of system resources. Even relatively simple
`
`BACKGROUND OF THE INVENTION
`The past decade was a revolutionary time in computing.
`The advent and proliferation of personal computers has
`transformed the computer environment ?'om one of large
`mainframe computer systems which were highly centralized
`and tightly controlled. to a network of interconnected per
`sonal computers and workstations which are often widely
`distributed. yet easily accessible. via computer networking.
`Concomitant with this change in computer environments
`is the signi?cant expansion in the types of computer appli
`cation programs. In the past. computers provided. primarily
`accounting. data reduction. and data-base management func
`tions. In addition to these applications. computers now
`provide voice messaging. games and multimedia applica
`tions for business and educational use. While older computer
`application programs could be accommodated using com
`puter systems capable of displaying only text type data. the
`new computer application programs require computer sys
`tems capable of displaying graphical. audio and video data
`to create today’s multi-media environments.
`Unlike text information. graphical and in particular video
`and audio data require signi?cant amounts of data storage.
`As an example. to display a color video image on a computer
`monitor a large amount of digital storage is required to store
`the digitized data indicative of the color image in compari
`son to text information.
`FIG. 1 illustrates a well known system architecture for a
`multi-media capable computer system 100. such as an IBM
`PSI2® personal computer (“PC"). The computer system 100
`includes a central processing unit (CPU) 102 which includes
`a microprocessor (e.g.. a 80x86. a Pentium. PowerPC. etc.
`.
`. .). read only memory (ROM) 104 and random access
`memory (RAM) 106. The computer system also includes a
`memory controller 103 which controls system RAM 106. a
`bus controller 112 which controls a system bus 108. and an
`interrupt controller 114 which is used for receiving and
`processing various interrupt signals.
`Mass storage may be provided by a diskette 1103. a
`CD-ROM disk 109B or a hard disk 113b. The diskette 110B
`can be inserted into a diskette drive 110A. which is. in turn.
`connected to the system bus 108 by a disk driver controller
`110. Similarly. the CD-ROM disk 109B can be inserted into
`a CD-ROM drive 109A. which is also connected by a
`controller 109 to the system bus 108. Finally. hard disks
`1138 are part of a ?xed disk drive 113A. which is also
`connected to the bus 108 by a controller 113.
`Input and output to computer system 100 is provided by
`a number of devices. For example. a keyboard and mouse
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`Ex. 1010 / Page 9 of 16
`
`

`
`5 342.797
`
`10
`
`20
`
`25
`
`4
`The amount of display memory required for the frame
`buffer 111B depends upon the number of pixels on the
`display 111A and the amount of data required for each pixel.
`Often. the engine includes more display memory than is
`needed for the frame buifer 111B. Although this “extra”
`display memory capacity may be implemented in VRAM,
`DRAM. SRAM. or other memory technology. the extra
`capacity is typically. collectively called “o?-screen
`VRAM.”
`Olf-screen VRAM 111D. like the frame buffer 111B. is
`proximal to graphics engine 111C and may transfer data to
`and from the graphics engine without using the system bus
`108. Consequently. the engine 111C may access data more
`e?iciently in off-screen VRAM 111D than data in system
`RAM 106. because the engine 111C does not incur the
`performance penalty associated with using the bus 108 and
`CPU to retrieve data. This aspect is often exploited to
`improve performance by a technique called “caching.” The
`more often particular data are used by engine 111C. the
`greater the performance advantage of caching. or storing.
`that data in off-screen VRAM 111D. Typically. mouse cursor
`information or font information is cached. Newer
`techniques. discussed in the detailed description. also exploit
`the performance advantage associated storing data in off
`screen VRAM 111D.
`Although the cost per bit of computer memory has
`dropped signi?cantly in the past several years. the off-screen
`memory storage requirements for new software multimedia
`applications packages has grown signi?cantly primarily due
`to the growing use of video and audio capable personal
`computer systems.
`However. the prior art techniques for allocating and
`deallocating regions of o?i-screen VRAM 111D are less than
`desirable to ensure that off-screen VRAM is used as effi
`ciently as possible.
`As an example. prior art off-screen video memory man
`agement techniques have generally managed the allocation
`of regions (i.e.. addressable areas) of the display memory
`using a static allocation process which performs the alloca
`tions at compile time. Compilation lime is the event of
`translating the source code as written by the programmer
`into machine executable format. As expected by virtue of its
`name. a disadvantage with static allocation is that the
`allocations of video memory when made at compile time
`remain in?exible even as the requirements for video
`memory change due to computation.
`To e?iciently utilize the amount of video memory avail
`able in a computer system. a memory manager system must
`allocate off-screen video memory in a more efficient manner
`to ensure proper utilization of the valuable otf-screen portion
`of the video memory.
`
`3
`graphical items. such as lines and circles. may require
`considerable computation to determine which pixels should
`be illuminated. For example. the well known algebraic line
`equation. y=mx+b. is typically unsuitable for use as a
`graphics equation because it often yields a line having an
`appreciable “staircase eifect.” Consequently. over the years.
`mathematicians and designers have developed “graphics
`equations” peculiarly suited to the needs of a discrete.
`pixel-oriented display 111A. Though these equations yield
`higher quality graphic items. they are computationally inten
`sive.
`Animated video may involve relatively less computation.
`but usually requires considerably more storage resources
`and system bus 108 bandwidth. Animated video is produced
`by displaying a sequence of video frames at a sul?cient
`playback rate. such as ?fteen video frames per second. to
`yield a relatively continuous image.
`Because a typical a video frame may involve thou sands to
`millions of pixels. the storage and bandwidth problems
`quickly become critical. To help alleviate the storage and
`bandwidth burdens. special video data formats and com
`pression and decompression techniques have been devel
`oped. With such systems. compressed video data are
`retrieved from the system RAM 106. There. the compressed
`data may be decompressed by a software decompression
`routine (not shown). Afterwards. the decompressed data is
`placed in the frame buffer 111B for display. In some cases.
`the decompressed data is “stretched” a prede?ned amount by
`a software stretch routine. and the stretched image is placed
`in the frame buffer 111B. In a well known manner. stretching
`techniques allow a smaller image to be stored in off-screen
`video memory. and retrieved and a larger image before being
`placed into the frame bu?er to be displayed
`IBM has developed the Ultimotion'm. an all software. full
`motion video data system. which. among other things.
`provides software routines to compress. transmit and
`decompress frames of video data according to the Ultimo
`tion data format. Each video frame may be either an “intra”
`frame or a “delta" frame. An intra frame is representative of
`an entire image to be displayed. A delta frame is represen
`tative of only changes to the prior image frame. Though
`Ultimotion and other systems have alleviated some of the
`system resource requirements associated with motion video.
`a substantial amount of resources are still required. such as
`off-screen VRAM.
`To support the demands for enhanced graphics and video
`in today’s computer systems. a considerable effort has been
`made in developing graphic engines 111C to further reduce
`the computational burden placed on the CPU 102 and the
`system bus 108. Typically. the graphics engine 111C (also
`often referred to as a “graphics coprocessor”. or a “graphics
`accelerator”) includes its own internal display memory and
`special purpose hardware to determine which pixels should
`be energized in response to a graphics command and to store
`the appropriate display data in the frame buifer 111B. For
`example. the graphics engine 111C may have special hard
`ware (i.e.. a dedicated integrated circuit) to implement a
`graphics line equation to determine which pixels should be
`energized to display a line. in response to a command to
`draw a line. Conventional engines 111C typically further
`include functionality to draw circles and rectangles. as well
`as having the capability to ?ll areas with color and “clip”
`images. Besides freeing the CPU 102 from having to per
`form the computational operations involved with the graph
`ics equations. the engine 111C frees the system bus 108 from
`having to transfer considerable amount of display data to the
`frame buffer 111B.
`
`35
`
`45
`
`55
`
`65
`
`SUMMARY OF THE INVENTION
`An object of the present invention is to locate and
`deallocate off-screen display memory in a manner which
`optimizes the amount of available display memory in a
`computer system.
`According to the present invention a display memory
`manager allocates and deallocates off-screen display
`memory in response to allocation and deallocation requests.
`by dividing the memory space into a plurality of non
`overlapping regions each capable of storing a different
`amount of video data indicative of a video image. and
`creating a linked list data structure indicative of the allocated
`and unallocated regions and various combinations of the
`unallocated regions. Upon receiving a request for memory.
`
`Ex. 1010 / Page 10 of 16
`
`

`
`5.742.797
`
`10
`
`20
`
`25
`
`35
`
`45
`
`5
`the memory manager traverses the linked list data structure
`searching for a region or combination of regions large
`enough to store the requested mount of display data. Once
`a region or combination of regions has been found and
`allocated. the linked list data structure is updated to indicate
`that the new region or regions are now allocated and hence
`unavailable to a subsequent requested allocation unless
`deallocated.
`The display memory manager of the present invention
`maintains a “snap shot” of: 1) the region in the o?-screen
`display memory space which are currently allocated for
`storing video information. 2) the unallocated regions in the
`off-screen display memory and 3) the various combinations
`of the unallocated regions in otT-screen display memory.
`Information indicative of each allocated and unallocated
`region. and the combination of unallocated regions is main
`tained in a linked list data structure. Each element in the
`linked list is associated with a region or combination of
`regions and each element contains ?elds indicative of the
`region’s starting address. its size and whether or not the
`region is currently allocated.
`Upon receiving a request for a region of off-screen display
`memory. the display memory manager determines the region
`in display memory which is the best ?t for the information
`to be stored. The memory region of best fit is determined by
`traversing the linked list structure which is organized from
`smallest available sized region to largest sized memory
`region or combination of region. Starting with the smallest
`region. the display memory manager checks the elements of
`the list arranged according to size in sequential ascending
`order. Once the smallest unallocated region of sui?cient size
`has been found the region is allocated
`By arranging the linked list elements starting with the
`smallest region to the largest. traversing through the list in
`sequential order ensures that the selected region is the best
`?t for the new information to be stored.
`The linked list may be a singularly linked list since the
`preferred process for determining the region of best ?t
`involves starting with the ?rst element and sequentially
`checking as necessary the elements associated with large
`regions. However. a doubly linked list may also be used if
`one wishes to use a ditferent search process to determine the
`region of best ?t. The use of a doubly linked list may in fact
`facilitate inserting. deleting and reorganizing the elements in
`the list since each element in the list will include two
`pointers. one to each adjacent element.
`The present invention is applicable to bit-mapped. pixel
`packed and other display formats.
`The display memory management system of the present
`invention results in e?icient utilization of the available
`display memory space due to its dynamic and ef?cient
`allocation/deallocation process for multitasking operating
`systems.
`By controlling the allocation and deallocation of display
`memory. arbitration of the memory is inherently performed.
`These and other objects feature and advantages of the
`present invention will become more apparent in light of the
`following detailed description of a preferred embodiment
`thereof. as illustrated in the accompanying drawings.
`BRIEF DESCRIPTION OF ‘THE DRAWINGS
`FIG. 1 is an illustration of a block diagram of a video
`capable computer system;
`FIG. 2 is an illustration of functional block diagram of
`some of the computer system components involved in
`displaying information on the computer system;
`
`55
`
`65
`
`6
`FIG. 3 illustrates a linked list data structure containing
`several ?elds of information indicative of each allocated and
`unallocated region in off-screen video memory;
`FIGS. 4A-4D are pictorial illustrations of the off-screen
`display memory partitioned into allocated and unallocated
`regions;
`FIGS. SA-SB together form a ?ow chart of the off-screen
`display memory allocation process; and
`FIG. 6 is a ?ow chart of the o?-screen display memory
`deallocation process.
`
`DETAILED DESCRIPTION
`FIG. 2 is an illustration of functional block diagram of
`some of the computer system components (hardware and
`software) involved in displaying information on the com
`puter display 111A. The components are preferably embod
`ied in a multimedia capable computer system. such as the
`computer system shown in FIG. 1. executing 05/2“. or a
`similar multi-tasln'ng operating system. The system gener
`ally includes a plurality of application programs 201A.
`201B. . .
`. which are executed in the CPU 102.
`More particularly. the application programs 201 may
`include a word processing program having text data. a
`spread sheet package with graphics. and a video editing
`package which displays video images on the display. While
`executing. the application programs may invoke in a well
`known manner various software routines from a software
`library 202. The routines within the library 202. in turn.
`communicate with a device driver 203 which is a hardware
`speci?c software routine responsible for communicating
`with a display controller 211 (e.g.. a super VGA card). The
`display controller 211 includes a graphic engine 211C.
`off-screen display memory 211D (e.g.. VRAM). and a frame
`bulfer 211B (also referred to as on-screen VRAM). As
`known. the frame buffer 211B is sequentially scanned by the
`controller 211 to provide a graphical or animated image on
`the display 211A.
`The software library 202 includes routines that are com
`monly needed by application programs 201. As such. appli
`cation program development is facilitated. became an appli
`cation developer does not have to design. develop. test. and
`debug routines that are commonly needed. such as decom
`pression routines. color conversion routines. software imple
`mentations of graphics equations. and the like. The devel
`oper need focus only on the peculiar aspects of the
`application program being developed.
`If necessary. the application programs 201 need not use
`library 202. but instead may directly communicate with the
`device driver 203. if the applications 201 have the appro
`priate system privileges. To better focus the remaining
`description on the various aspects of the invention. the
`combination of the application programs 201 and the library
`202 will hereinafter be referred to as “requesting software”
`205.
`The device driver 203 is hardware-speci?c software that
`communicates with display controller 211. The device driver
`203 includes a set of entry points. or “exports.” at which the
`driver 203 may be invoked. or called. Each entry point has
`an associated software routine that corresponds to a particu
`lar function performed by the driver 203. For example.
`according to the present invention the driver 203 includes an
`entry point to an o?- screen display memory manager routine
`203A dedicated to allocating and deallocating regions of
`off-screen VRAM 211D.
`Each routine associated with an entry point expects to
`receive certain “in parameters" as part of the call: likewise.
`
`Ex. 1010 / Page 11 of 16
`
`

`
`5.742.797
`
`20
`
`30
`
`35
`
`10
`
`7
`the calling code. e.g.. the requesting software 205. expects
`to receive certain “out parameters” from the routine. as well
`as expecting that the routine will “return” with return codes
`according to a prede?ned interface. The return code may
`indicate that an error was encountered. that the request was
`successfully serviced. or that the request was partially ser
`viced.
`Device driver 203 may use known device “helper” rou
`tines 204 in order to perform its tasks. Helper routines 204
`are provided by many operating systems. including 08/2. to
`facilitate the development of device drivers. by providing
`commonly needed routines. In this respect. they are some
`what analogous to the library 202 discussed above.
`According to the present invention. software 205 requests
`a region of butfer memory. or a contiguous portion of
`olT-screen VRAM 211D. by calling the off-screen display
`memory manager 203A which controls the allocation and
`deallocation of off-screen display memory (e.g.. VRAM).
`The “in parameters” for this entry point may include a
`function code indicating whether a buffer is being requested
`or deallocated. the desired size of the buffer. a buffer id. the
`requester handle. and the type of buffer desired. The “out
`parameters” from the routine may include the size of the
`allocation actually performed and an o?-screen VRAM
`25
`address.
`The allocation call may be made during initialization of
`one of application programs 201. for example. As suggested
`above. the buffer. once allocated. may be used by the
`requesting software 205 to improve performance by caching
`cursor information. or storing decompressed. video data. for
`example.
`The data stored in the off-screen display memory is
`generally indicative of an image in a compressed format. and
`contains a plurality of pixels which are bit-mapped. If the
`image is non-gray scale monochrome. the bit mapped image
`can be represented simply as a two dimensional image since
`each pixel needs only one bit of information to indicate
`whether the pixel is on or o? (i.e.. illuminated or not
`illuminated). However. if the image is either a gray scale
`image or a color image. several bits are required to represent
`each pixel location. As an example. in a monochrome
`system having 256 shades of gray or a color system having
`256 color modes. eight bits are required for each pixel
`location.
`FIG. 3 illustrates a linked list 302 with a plurality of
`elements 304-307 each containing several ?elds 3104312 of
`information indicative of each allocated and unallocated
`region in off-screen display memory 211D (FIG. 2). Each
`element 304-307 in the linked list 302 corresponds to a
`speci?c region or combination of regions in the o?i-screen
`display memory 211D and contains ?elds 310-312 indica
`tive of the region location in memory space. whether the
`region is allocated or not. and the size of the region
`respectively. The elements 304-307 of the linked list are
`arranged from smallest region to largest region or combi
`nation of regions. The linked list is preferably a singly linked
`list. but one of ordinary skill will realize that a doubly linked
`list may also be used.
`Upon receiving a request for a region of olT-screen display
`memory. the o?-screen display memory manager 203A
`determines the region in off-screen display memory 211D
`which is the best ?t for the information to be stored. The
`memory region with the best ?t is determined by traversing
`the linked list 302 structure which is organized according to
`region size from smallest available sized region to largest
`sized memory region or combination of regions. Starting
`
`8
`with the smallest region. which is the ?rst element 304 in the
`linked list. the off-screen display memory manager 203A
`checks the elements of the linked list in ascending order
`arranged according to region size. Once an unallocated
`region of su?icient size has been found. the region is
`allocated. By arranging the regions according to size starting
`with the smallest region. a traversal through the linked list
`302 in this order ensures that the selected region is the best
`?t for the new information to be stored.
`FIG. 4A illustrates the off-screen video memory 211D
`partitioned into an allocated region 402 for video image #1
`and an unallocated region 404. This represents the ?rst
`allocation in response to an allocation request from the
`requesting software 205. The linked list structure indicative
`of this partitioning of memory would contain two elements.
`Since the allocated region 402 is smaller than the region 404.
`the ?rst element in the linked list 302 (FIG. 3) would
`correspond to the allocated region 402 of memory. The
`allocated region 402 would contain the necessary amount of
`contiguous memory locations to satisfy the requested
`amount. The second element in the linked list would contain
`the starting address for the unallocated region 404. along
`with the size of the unallocated region and a boolean status
`?ag indicating that the region is unallocated.
`Assuming two more allocation requests have been
`received and performed without a deallocation request. FIG.
`4B illustrates the off-screen video memory 211D partitioned
`into regions 402. 406-407 for storing video images #1-#3
`respectively. The linked list 302 (FIG. 3) for this partitioning
`would include four elements; one for each of the allocated
`regions 402.406-407 and one for the unallocated region 404.
`Each element would include its respective region‘s size. the
`regions starting addres