United States Patent [191
`Notarianni
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005404511A
`[tt] Patent Number:
`[45) Date of Patent:
`
`5,404,511
`Apr. 4, 1995
`
`[75]
`
`[54) COMPACT DISC PLAYER WITH
`FRAGMENT MEMORY MANAGEMENT
`Inventor: Benedetto A. Notarianni, Reigate,
`England
`[73) Assignee: U.S. Philips Corporation, New York,
`N.Y.
`[21] Appl. No.: 904,771
`Jun. 26, 1992
`[22] Filed:
`Int. C1.6 .............................................. G06F 15/20
`[51)
`[52] u.s. Cl •...................................... 395/600; 369/32;
`369/47
`[58] Field of Search ............... 395/425, 600, 325, 164;
`369/32,47,33,30,25,14
`References Cited
`U.S. PATENT DOCUMENTS
`4,912,629 3/1990 Shuler ................................. 395/600
`5,109,336 4/1992 Guenther ............................ 395/425
`5,148,527 9/1992 Basso ................................... 395/425
`
`[56]
`
`OTHER PUBLICATIONS
`Wilson, "Uniprocessor Garbage Collection Tech(cid:173)
`niques", Proceedings: Memory Management. Interna(cid:173)
`tional Workshop IWMM 92, pp. 1-42 (Springer Verlag
`Sep. 23, 1992).
`Edited by Philips International & published by Kluwer
`Technical Books, ISBN 90 201-21103, entitled: "CD-I:
`A Designer's Overview", Chapter 7 1987.
`P. Dibble, "OS-9 Insights: An Advanced Programmers
`
`Guide to OS-9/68000", Chapters 3 & 4, published by
`Microwave Systems Corporation,
`ISBN 0-9180-
`35-0105 1991.
`
`Primary Examiner-Thomas G. Black
`Assistant Examiner-Jennifer M. Orzech
`Attorney, Agent, or Finn-Anne E. Barschall
`
`ABSTRACT
`[57)
`An application module of a data processing apparatus
`requires various quantities of memory space for the
`buffering of data to be processed. In particular, image
`and audio files are to be read from a CD-ROM disc and
`decoded in real-time. The operating system provides a
`· memory manager to allocate buffer space from the
`available memory. To alleviate the problem of fragmen(cid:173)
`tation, a fragmented memory manager module secures
`at the outset an allocation of buffer space sufficient for
`all requirements of the application module, and parti(cid:173)
`tions the allocation into small units of buffer space (frag(cid:173)
`ments), which are linked into a list by respective list
`pointers. Any subsequent requirement for buffer space
`is met by the fragmented memory manager, by un-link(cid:173)
`ing the requisite number of fragments from the list of
`unallocated fragments. The application module
`is
`adapted to use fragmented buffer space where possible,
`while the allocation of buffer space in contiguous blocks
`is not excluded when necessary.
`
`FRAGM
`
`CD RTOS
`MEMORY
`MANAGER
`
`- f-- 210
`
`I
`
`I
`A
`B -,--~
`FMV
`-
`
`DECODE
`
`1
`I
`J----J
`I
`
`VDA~
`WB
`ADPCM FMV
`
`APPLICATION
`MODULE
`
`PCB
`--zoz
`
`FRA6 LISTS
`
`2)2
`
`zoo- ~ RAM
`
`3 Claims, 7 Drawing Sheets
`
`CD RTOS
`
`PLAY CONTROL
`MODULE
`
`,. ~zoe
`
`zo~
`'
`COP
`
`i<
`I
`
`206'-
`=:>
`
`Page 1 of 14
`
`ZTE Exhibit 1031
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 1 of 7
`
`5,404,5Jl
`
`COP
`
`LSL
`
`LSR
`
`0
`
`MPU
`
`DMA
`
`NV RAM
`
`C/C
`
`CDRTDS
`
`YOU
`
`0
`
`VRGB
`
`RAM
`
`INP
`
`KB
`
`(PRIOR ART)
`FIG.1
`
`Page 2 of 14
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 2 of 7
`
`5,404,511
`
`APPLI CAliON
`MODULE
`
`PCB
`
`•t- 202
`
`CD RTOS
`
`PLAY CONTROL
`MODULE
`
`.. ~zoe
`
`zoo- -RAM
`
`I
`;
`A B ,,.--=.1
`
`FRA6 LISTS
`
`2)2
`
`FRAGM
`
`FMV
`
`CD RTOS
`MEMORY
`MANAGER
`
`- f- 210
`
`(PRIOR ART)
`304
`
`~
`
`zo~
`COP
`
`DECODE
`
`206'-
`'
`1
`-v
`I
`VDA/
`I
`J----J
`WB
`ADPCM FMV
`
`· Fl G. Z
`
`302
`
`AUD.2
`
`~
`
`RAM
`
`Fl6.3
`
`Page 3 of 14
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 3 of 7
`
`5,404,511
`
`_0
`
`300
`
`FRAILPREVP
`BUFFER
`2324 BYTES
`-
`
`-
`
`.,
`-~
`
`PCL+
`
`r'FRAG
`fPCL+
`
`.;
`
`/ / / /
`I
`r--
`,I
`[/
`
`I
`
`I
`
`I
`
`l t II llf f IIi~
` BUFFER, ,....,..._.
`I
`I
`I ,
`I
`
`/ v
`
`I
`
`PCL_CTRL
`PCl-SMODE
`PCL_TVPE
`. PCL_SIG
`PCL_NXT
`PCL_BUF
`PCL_BUFSZ
`PCL_ERROR
`PCL_CNT
`FRAG_PREV -
`
`I I I I
`-
`r-..
`t-- I I
`I
`I/
`
`.
`
`I
`
`I
`
`FIG.4
`
`FRAGM 212
`
`FR~E-A
`
`FRAG_INIT
`
`FRAG_GRAB
`
`FRAG-FREE
`
`FIG.5
`
`Page 4 of 14
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 4 of 7
`
`5,404,511
`
`700
`
`APPLICATION MODULE
`
`702
`
`®
`
`®
`
`706
`
`FRAG_GRAB
`
`(NSECT)
`
`708
`
`DEFINE PCB, CIL
`
`710
`
`-PLAY (FILE, PCB)
`
`712
`
`FRAG_ FREE
`
`-©
`-®
`
`(IMZ)
`
`714
`
`FRAG _ SHUTDOWN
`
`716
`
`FIG.6
`
`Page 5 of 14
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 5 of 7
`
`5,404,511
`
`800
`
`804
`
`806
`
`860
`
`862
`
`864
`
`RELEASE
`ALLOC.
`
`840
`
`842
`
`844
`
`846
`
`848
`
`850
`
`FIG.7
`
`Page 6 of 14
`
`

`
`300./":\
`
`-
`
`1,:::;.
`
`I
`
`-
`
`r
`II
`
`"~ -
`I
`
`I
`
`f:.
`
`-
`
`r
`II
`
`-
`
`r
`I I
`
`-
`
`r
`I I
`
`-
`
`r
`I I
`
`-
`
`-
`r
`._,
`~ r
`r
`if i l l t l
`
`PCL_NXT
`0
`FRAG-PREV
`
`i
`
`Cll UM2)
`r
`.
`..,_,
`I AUt3
`IIM2.1
`..,
`
`~·u· j
`
`~
`
`,-_'()'
`IIM2.2
`
`,
`\{
`IIM23I
`
`F3
`
`,,.·a l
`ro·
`r
`I'
`I
`IM2.4 I IM2.5 II F4
`
`I
`
`®
`
`®
`
`. ··--
`I Fl
`fAU1.2
`·o·~
`
`''
`
`®
`
`I F6
`
`r,
`I AU1.2
`\
`
`1)-
`
`'
`AU1.1 I F2
`'
`CLI(AUl)
`.
`
`AUl.l
`
`F7
`"'
`·o·
`
`FREE
`·'
`,,
`
`Fl
`
`·o·
`
`rr·n·
`' r
`I AU1.3 I F2
`
`,,
`
`"'-·
`••
`
`FJ
`
`. I'
`IFB
`
`F4
`
`I FS
`I
`
`'0'
`II
`I
`
`F9
`
`.
`'
`
`...;
`
`FIG.8
`
`~ •
`rJ'1 •
`
`""d i
`
`t
`
`,_.,J;;I.
`
`1-l
`
`~
`
`r ~
`
`0\
`
`s,
`......:.
`
`...
`Ul
`~ = ~ ...
`....
`....
`
`Ul
`
`Page 7 of 14
`
`

`
`300
`2 -
`
`.
`
`'
`
`• •
`
`·
`
`PCL NXT
`
`900
`FREE~
`
`FRAG_PREV
`
`'0'
`
`®- WAI Fer FZ u Fl u F4 u F5 n F6 0 F7 0 FB tl@djf@l F9tf
`rr - 'l
`f.-
`'
`PCL-NEXT
`® ~I
`BUFFER I ~~~~ II
`- - - - - - - - - PCL-BUFF
`FRAG-PREV
`PCLBUFSZ=6
`FRAG_PREV•'O'
`
`FIG.9
`
`~ • 00. •
`"'C a a
`~
`
`.. ~
`'"""' ~ (II
`
`00 =-
`m.
`-...l
`a,
`-...l
`
`(I)
`
`...
`~ .a;:..
`...
`
`(I)
`~
`~
`
`Page 8 of 14
`
`

`
`1
`
`5,404,511
`
`COMPACI' DISC PLAYER WITH FRAGMENT
`MEMORY MANAGEMENT
`
`2
`taining by means of said list pointers a linked list of
`unallocated fragments (the "free list");
`(b) in response to each subsequent request for alloca(cid:173)
`tion of a quantity buffer space, un-linking from the free
`The invention relates to dynamic allocation of buffer 5 list a list (the "allocated list") of fragments sufficient in
`number to contain the requested quantity of buffer
`space in the memory of a data processing apparatus.
`The invention has particular utility in so-called interac-
`space; and
`(c) in response to a subsequent request for release of
`tive systems, where audio, video and other data items
`are to be decoded and presented to a user in real-time.
`the allocated list of fragments re-linking the allocated
`In many data processing apparatuses, data is read 10 list of buffer fragments into the free list.
`By managing the memory from the outset as a set of
`from a database stored in some form of mass memory
`(for example a magnetic disc or Compact Disc read-
`many small fragments, any small fragment can be uti-
`only memory (CD-ROM) and transferred to local mem-
`lised to contribute to any allocation of buffer space,
`ory (RAM) for processing. Local memory is limited,
`large or small (minimum size: one fragment). Of course
`however, and it is generally unpredictable what items of 15 the allocated buffer may be the sum of many fragments
`data need to be loaded at any given time, and what is the
`dispersed randomly throughout the physical memory
`size of each. Therefore it is necessary to provide some
`space. This need not be a problem, however, because
`memory management function, which keeps track of
`the list pointers can be used by the apparatus in access-
`the available memory and allocates buffer space in re-
`ing the allocated buffer space. It will be appreciated that
`20 fragmentation no longer prevents allocation of a re-
`sponse to requests from application processes.
`quested quantity of buffer space.
`The Compact Disc-Interactive (CD-I) player, avail-
`able from Philips, is an example of a data processing
`In the CD-I apparatus, the CDRTOS play control
`apparatus in which memory management functions are
`function is already capable of using fragmented memory
`as buffer space by means of its play control structure.
`provided by a real-time operating system CDRTOS.
`CDRTOS is based on another real-time operating sys- 25 The invention is particularly valuable in such a case.
`Accordingly, a particular embodiment of the inven-
`tern OS-9/68000. The CD-I player operates under the
`control of an application program which is loaded from
`tion provides a real-time data processing apparatus
`a CD-ROM. Through some play control functions of
`comprising:
`CDRTOS, the application program can control access
`a database access means ("reader") for receiving from
`to a large database of images, sounds and other informa- 30
`a database data for processing in real-time;
`tion stored on the CD-ROM, under the interactive con-
`real-time data processing means ("decoder") for pro-
`trol of the user.
`cessing the data received from the database;
`A description of the CD-I player is provided in
`memory means coupled between the reader and the
`"CD-I: A Designer's Overview", edited by Philips In-
`decoder for providing buffer space for storing the
`ternational and published by Kluwer Technical Books, 35
`received data prior to processing by the decoder;
`ISBN 90-201-21103. This book is incorporated herein
`an application module for generating play commands
`by reference. The problems of memory management in
`to control the reader and decoder to process data in
`such systems are described for example in Chapter 3
`a desired sequence; and
`and 4 of the book "OS-9 INSIGHTS: An Advanced
`a play control module for receiving said commands
`Programmers Guide to OS-9/68000" by Peter Dibble, 40
`and for controlling the reader and decoder in real
`time so as to receive data from the database and
`published by Microware Systems Corporation, ISBN
`0-918035-0105.
`cause processing of said data in a real-time se-
`One particular problem highlighted in the Dibble
`quence defined by said commands,
`book is that of memory fragmentation. This occurs
`wherein each play command supplied to the play con-
`when, after a period of operation during which various 45 trol module includes (i) file information defining the
`location in the database of the data to be processed and
`parts of the memory have been allocated and de-
`allocated, the available (unallocated) memory at a given
`(ii) buffer information specifying the location in the
`time is made up of small areas dispersed effectively at memory of buffer space for storing said data, wherein
`random throughout the memory space. This fragmenta-
`the buffer information comprises at least one play con-
`tion might mean, for example, that a request for the 50 trol item containing fields for indicating the location of
`allocation of 60 kilobytes of buffer space cannot be
`a fust quantity of buffer space and a list pointer to an
`optional further play control item, wherein the play
`satisfied because there is no single unallocated block
`larger than 50 kilobytes. At the same time, adding up all
`control module is responsive to said play command to
`the small fragments, there may in fact be hundreds of
`cause the data defined by the file information to be
`kilobytes of unallocated memory.
`55 received from the database and stored in said first quan-
`The invention addresses the problem of providing
`tity of buffer space and in the event that said fust quan-
`tity of buffer space becomes full to use the list pointer in
`memory management in a data processing apparatus,
`for example to reduce the problem of fragmentation
`the at least one play control item to identify a further
`play control item indicating a further quantity of buffer
`described above.
`The invention provides a method of dynamically 60 space for storage of the required data, and wherein the
`total of available buffer space in the memory is divided
`allocating and releasing variable quantities of buffer
`space in a memory of a data processing apparatus hav-
`into a plurality of fragments, each fragment containing
`ing a fmite total amount of buffer space, the method
`a relatively small predetermined quantity of available
`comprising:
`buffer space and having an associated play control item
`(a) in an initialization step (i) partitioning the total 65 with a list pointer identifying a further fragment con-
`taining available buffer space, the apparatus yet further
`unallocated buffer space into a set of small buffer frag-
`ments, maintaining for each unallocated fragment a
`comprising a fragmented memory manager module for
`respective list pointer; and (ii) constructing and main-
`maintaining by means of the play control item list point-
`
`Page 9 of 14
`
`

`
`5,404,511
`
`4
`3
`book "Compact Disc-Interactive, A Designer's Over-
`ers a list of those of said fragments whose buffer space
`view" mentioned above.
`is not currently in use by the play control module (the
`In the CD-I player, the operating system CDRTOS
`"free list") and for responding to each request for allo-
`controls the operation of the various hardware elements
`cation of buffer space by un-linking from the free list a
`list of fragments (the "allocated list") and supplying to 5 in real-time, under the control of application programs
`the application module a pointer to the allocated list for
`loaded from the disc. The processing power of micro-
`use by the play control module in identifying buffer
`processor MPU is thus shared by application software
`modules and modules of CDRTOS, but in an asynchro-
`fragments for received data.
`In the case of CD-I, each fragment may conveniently
`no us manner such that each module can be regarded as
`contain enough buffer space for one sector of data from 10 an independent functional module of the player.
`FIG. 2 illustrates the interaction of various modules
`the CD-ROM, that is 2324 bytes. The memory con-
`sumed by storing so many list pointers will be only one
`in the CD-I player when implementing the present
`percent or so of the total memory space, which is trivial
`invention. Central to these functions is the memory
`compared to the amount of memory that can be wasted
`200. This
`comprises
`one megabyte
`(RAM)
`by fragmentation in a conventional memory manage- 15 (1024 x 1024 x 8 bits) of read-write memory, divided
`ment system.
`into two planes A and B. A third plane FMV is shown
`To illustrate ~he ab_ove and £u:fuer feature~ and ~d-
`dotted, which in future CD-I players will provide stor-
`v~tages of the m':ention, embodiments of the ~vent10n
`age for full motion video data.
`will now be descnbed, _by way ~f ex~ple,. wtth refer-
`An application module 202, defined by program data
`ence to the accompanymg drawmgs, m which:
`20 read from the disc player 204 (CDP), operates with
`FIG._1 shows the h~dware s~ructure o~ the d~ta
`assistance from CDRTOS to read audio, video and
`proc~ssln:g appara~ swtable for Implementing the m-
`program data from the disc into memory, and to cause
`vention, m the parttcul~ form of a CD-I player;
`the decoders 206 to read this data for the generation of
`FIG. 2 shows the logtcal structure of the apparatus of
`.
`.
`·
`·
`. all
`"th th .
`ti"
`25 desrred audto and vtdeo presentatiOns. Specific y,
`·
`tin.
`dan
`FIG 1
`f
`.
`, opera g m accor
`ce w1
`e mven on;
`d VDA
`·
`·
`d
`d VDB
`da
`vtdeo eco ers
`an
`rece1ve
`ta rom re-
`f
`FIG 3 ill
`th
`ta
`f
`bl
`t
`t
`an ° . e memory, w . e t e au o
`hil h
`.
`us ra es
`·
`A dB fth
`di
`e pro em o memory ragmen -
`1
`tion as it arises in the real-time control of the CD-I
`specttve Panes
`.
`.
`decoder ADPCM can recetve data from e1ther plane.
`player wtth conventional memory management;
`A
`.
`ti
`f CDRTOS · th
`all d
`f;
`. pnm~ ~c on ~.
`e S?-c ~
`FIG. 4 illustrates the partitioning of the memory into
`IS
`small fragments in the apparatus of FIGS. 1 and 2, and 30 playm~ of real time f~es . Such til~ can contain audto
`data, ~d~ data or ~ mterleaved miXture of the two, as
`shows the structure of one representative fragment;
`descnbed m the Philips/Kluwer tex~boo~. A pl~y co~-
`FIG. 5 shows the logical structure of a fragmented
`trol module 208 of CDRTOS recetves ms~ruct10ns. m
`memory manager module in the apparatus;
`the form of a file reference an~ play co_ntrol informat~on
`FIG. 6 is a flow chart representing the operation of
`an application module of the apparatus;
`35 an proceeds to. cause the reading, stonng and decoding
`of ~e ~ata wtthout further effort on the part of the
`FIG. 7 comprises four flow charts representing the
`operation of elements of the fragmented memory man-
`application module 202. A memory manager module
`ager of FIG. 6;
`210 of CDRTOS allows the _applicati_on module 202 to
`FIG. 8 illustrates the allocation of memory fragments
`reserve blocks of memory m a desrred plane of the
`at points (A), (B), (C) and (D) in the flow chart of FIG. 40 ~emory 2~0, which can _be used as buff~rs storing the
`7· and
`vtdeo/audto data for a gtven play operatiOn.
`~e elements of FICJ:. 2 as described so far are co~-
`'FIG. 9 illustrates the allocation of contiguous blocks
`of memory within the fragmented memory of the appa-
`ventional. In a conventional arrangement, as the appli-
`cation module progresses in its operation, controlled by
`ratus.
`FIG. 1 is a block schematic diagram of the Compact 45 interaction with the user of the CD-I player, the prob-
`.
`.
`Disc-Interactive (CD-I) player. It comprises a compact
`lem of "~emory fragmentation" arises.
`disc player CDP to which is connected a compact disc
`FIG. 3 illustrates the problem of fragmentatiOn m the
`digital audio controller decoder CDDA and a compact
`playing of real-time files in a CD-I player, according to
`disc control unit CDCU. The CDDA is connected to an
`conventional practice. Sections of one plane of RAM
`audio processing unit APU which feeds two loudspeak- 50 are shown, with an arrow 300 indicating the direction of
`ers LSL and LSR. The CD control unit CDCU is con-
`increasing memory address. Parts of the address space
`nected to a system bus SB along which various digital
`which are free (not allocated by CDRTOS memory
`signals are passed. Also connected to the system bus SB
`manager) are indicated by cross-hatching (302 etc.).
`are a microprocessor unit MPU, a DMA controller
`Parts presently allocated for unspecified purposes are
`DMA, a non-volatile random access memory NVRAM, 55 shown by simple hatching (304). Other blocks contain-
`a clock calendar unit C/C, a read-only memory contain-
`ing buffer spaces IM.1, IM.2, IM.3, AUD.1 and AUD.2
`ing the real-time operating system CD RTOS, a key-
`have been allocated as buffer areas for the purpose of
`board KB, a pointing device INP, and an access con-
`storing video and audio data read from the disc.
`troller AC. The access controller controls the reading
`A play control structure is also constructed in mem-
`from and writing to a random access memory RAM 60 ory by the application module 202. This comprises a
`Play Control Block (PCB), a Channel Index List (CIL)
`which is split into two banks A and B. The access con-
`treller is also connected to a video decoder VD which
`for video, a CIL for audio and a set of Play Control List
`in turn feeds a video generator VRGB, the output of
`items (PCLs). The application module 202 supplies the
`play control module 208 of CDRTOS with one or more
`which is connected to a video display unit VDU. Also
`connected to the system bus SB is an adaptive pulse 65 file references (pointers to data locations on the disc 24),
`code modulation decoder ADPCM which feeds the
`and a pointer to the PCB. From then on the reading,
`audio processing unit APU. A description of the CD-I
`storage and d~coding of the files is automatic, barring
`base case decoder as shown in FIG. 1 is given in the
`intervention by the application module.
`
`Page 10 of 14
`
`

`
`5,404,511
`
`6
`5
`image, for example. This first PCL item in turn points
`The PCB area contains various control and status
`(by field PCL-NXT) to a second PCL item, which
`fields, including channel identifiers and pointers to the
`describes the buffer area for data IM.2, perhaps a sec-
`two CILs. By changing the channel number, the partie-
`ond image. The second PCL points to a third PCL
`ular audio and/ or video data read from the disc can be
`selected to account for the language preference of the 5 describing the buffer for data IM.3. The third PCL
`user, as described in the Philips/Kluwer textbook. For
`points back to the first PCL 308, thereby defining a
`a given channel, each CIL has a pointer to a PCL item,
`continuously repeating series of three images.
`as shown. The PCL structure in particular is relevant to
`The CIL(AUDIO) 310 points to a list of two PCLs,
`an understanding of the present embodiment, and will
`describing the buffers for data AUD.1 an AUD.2 re-
`now be described.
`10 spectively. The second of these audio PCLs contains a
`Each PCL item points to an area of memory which is
`null pointer '0' in the field PCL-NXT, indicating no
`to be used as a buffer, and contains the following fields:
`further sound data to be played. As mentioned above,
`PCL-CTRL: This field is initialized to zero by the
`the application module can halt or modify the playback
`application module before the play command is issued.
`by altering various fields in the play control structure.
`It contains status flags for use by CDRTOS, in particu- 15 Now, in the course of the interactive operation of the
`lar to note when an error occurs in reading data into the
`player under control of the application module and the
`corresponding buffer, or when the buffer is full.
`user, buffers of different sizes are allocated and released
`PCL_SMODE: This field is updated by CDRTOS
`many times. This leads to the problem of memory frag-
`with the value contained in the submode byte of the
`mentation which can be seen in the status of the mem-
`subheader of the last sector read into this PCL.
`20 ory as illustrated in FIG. 3. The unallocated areas
`PCL_TYPE: This field is set by the CDRTOS and
`(cross-hatched) are small and scattered between the
`contains the coding information byte of the subheader
`allocated blocks. This means that a request to the
`of the last sector read into the buffer of this PCL. This
`CDRTOS memory manager 200 for a new allocation of
`field can be used by the application module for refer-
`a large buffer space cannot be satisfied, even though the
`25 total amount of unallocated memory may be sufficient.
`ence only.
`PCL_SIG: This field is initialised by the application
`The memory fragmentation problem can now be
`module and contains a signal number to be returned to
`addressed by operation of a Fragmented Memory Man-
`the application module when the buffer of the PCL is
`ager module 212 (FRAGM), shown in FIG. 2.
`full or an error has been detected in the data transferred
`FRAGM 212 actually partitions the memory into uni-
`30 form and small buffers ("fragments") and maintains a
`to the buffer.
`PCL-NXT: This is a pointer to a further PCL item.
`linked listing of all unallocated fragments to allow dy-
`A linked list of PCLs can be built by the application, but
`namic allocation of any total buffer size, regardless of
`need only contain one item. The list may be circular or
`the physical addresses of the individual fragments in the
`may be terminated by the entry of a null pointer in this
`memory 200. By making the links via PCL-like struc-
`field. The list of PCL's may be manipulated by the 35 tures, in this CD-I embodiment, the fragmentation be-
`comes effectively transparent to the play control mod-
`application module at any time during the execution of
`the Play.
`ule 208 of CDRTOS.
`PCL-BUF: This is a pointer to the buffer space in
`As shown in FIG. 4, a large area of memory is di-
`which the data from the disc is to be stored. It is the
`vided into data structures "FRAG". Each FRAG com-
`responsibility of the application module to make sure 40 prises a buffer large enough for one disc data sector
`(2324 bytes), followed by an augmented PCL structure
`that this points to an allocated data area large enough to
`hold all the data requested for this PCL. If this pointer
`(PCL+ ). The various fields of the PCL structure are
`is zero, the data is not transferred into memory and
`provided, with the meanings as described above. This is
`PCL-CNT (see below) is not incremented.
`augmented however by an additional pointer field
`PCL-BUFSZ: This field specifies the size, in sectors, 45 FRAG-PREV.
`FIG. 5 shows the logical structure of the fragmented
`of the buffer pointed to by PCL-BUF. This field is
`initialized by the application, and may be changed by
`memory manager module 212 (FRAGM) which in-
`the application at any time during the execution of the
`eludes
`functions FRAG-INT, FRAG-GRAB,
`play command. A sector, as read from the disc, contains
`FRAG--FREE and FRAG_SHUTDOWN. These are
`up to 2324 bytes of data (CD-ROM Mode 2, Form 2). 50 activated by the application module 202, for example by
`PCL-ERR: This field points to an error information
`respective software function calls. For each plane of
`structure. If this field contains a zero (No error informa-
`memory (A,B, FMV, etc) FRAGM maintains a pointer
`tion structure available) a "Data error" bit is set in
`variable FREE-A, FREE-B, etc. For the purpose of
`PCL-CTRL, otherwise information about the data in
`simplicity, the following description makes no distinc-
`error is also returned in the given buffers. These data 55 tion between planes, except as explicitly mentioned.
`The operation of the various modules 202-212 in
`can be used to conceal error in video sectors for in-
`accordance with the invention will now be described
`stance.
`PCL-CNT: This field contains the offset in bytes
`with reference to the flow charts of FIGS. 6 and 7. To
`into the buffer of the next position to copy data. It
`assist in an understanding of their operation, FIG. 8
`should be initialized to zero by the application before 60 shows the status of memory allocation at four points
`(A),(B),(C) and (D) in the operation, as marked with
`the start of a play command. This field is updated by the
`system, but it may be changed by the application at any
`circled letters in FIG. 6. It should be appreciated that
`time during the execution of the play command.
`while there are only shown twelve memory fragments,
`Returning to the example of FIG. 3, then, the CIL(V-
`in practice hundreds of fragments can be allocated in
`IDEO) 306 points to a first PCL item 308 which in turn 65 the memory, each fragment giving 2324 bytes of buffer
`storage.
`points to a buffer reserved for video data IM.1. The
`buffer conventionally will contain enough space for
`In FIG. 6, the application module begins operation at
`serveral tens of disc sectors; enough for one complete
`700 when, for example, the user inserts a disc and a
`
`Page 11 of 14
`
`

`
`5,404,511
`
`8
`7
`826: The linking pointers PCL_NXT are followed
`CD-I application program is automatically read from
`and counted up to NSECT to identify the flfth free
`the disc and executed. The application program resides
`in one or other of the planes of the memory 200, but the
`fragment, and the FREE pointer is updated to indicate
`this fragment as the fust free fragment. Thus the four
`bulk of memory remains unallocated, to be used for
`s allocated fragments Fl..to F4 are unlinked from the free
`video and audio data.
`list and fragments FS to F12 now become Fl to F8. Null
`Rather than request allocation of buffer memory
`from the CDR TIS memory manager 210 in the conven-
`pointers are written accordingly to complete the un-
`linking. Upon return to the application module, the
`tional manner, as and when buffers are required, the
`application module first finds at 702 the maximum
`variable POINTER can be used to address a list of four
`amount of memory it will require in each plane. This 10 fragments, containing the requested four sectors of
`will normally be calculated at the time of writing the
`buffer space.
`application stored as part of the program. At 704, this
`At 708, the variable POINTER is copied to a CIL
`maximum size, expressed as a number MAXN of sec-
`entry CIL(IMl) as part of a Play Control Structure
`tors, is passed as a parameter to FRAGM, the frag-
`being defmed by the application module. A Play Con-
`mented memory manager module 212, in a call to the 15 trol Block (PCB) contains a pointer to the CIL for
`function FRAG-INIT. For each plane, the operation
`video, and another for audio, as described above in
`FRAG_INIT is shown in FIG. 7 as follows.
`relation to the conventional memory management oper-
`800: FRAG_INIT is activated by the application, in
`ations of CDRTOS. The situation of FIG. 8(B) now
`respect of a specillc memory plane (A, B, FMV etc.).
`applies, with the four allocated sectors of buffer space
`802: The parameter MAXN specilles how many sec- 20 being labelled IMl.l to IM1.4.
`At 710 the application module activates the play
`tors of buffer space might be required by the application
`at any one time.
`control module 208 ofCDRTOS, passing to it the loca-
`804: FRAGM requests CDRTOS memory manager
`tion of the PCB and identillcation of the disc location of
`210 to allocate at once the memory space required for
`four sectors of image data to be displayed. The play
`MAXN fragments.
`25 control module begins to read the identified sectors
`806: Assuming such memory space is available, the
`from the disc, and by means of the pointer CIL(IMl)
`address of the allocated space is received from the
`locates the flrst PCL item. This in turn points to the
`CDRTOS memory manager 210.
`buffer space IMl.l which has been allocated to receive
`808: The allocated space is "formatted" to create a
`the data.
`linked list of empty FRAG structures, each containing 30 After reading the fust sector of the image flle, of
`a buffer of2324 bytes and an augmented PCL structure.
`course, the play control module fmds the buffer IMl.l
`This format is shown at (A) in FIG. 8, with MAXN = 12
`full. Automatically it looks to the fleld PCL_NXT to
`leading to just twelve FRAG structures. The free buffer
`fmd a pointer to a further PCL, which in turn points to
`areas of these fragments are marked Fl to F12 in FIG.
`further buffer space IM1.2. By this process, all four
`35 sectors of the image flle are eventually loaded into the
`8(A).
`FRAGM creates a pointer variable 900 (FREE) for
`buffer sectors IMl.l to IM1.4. As described in the Phi-
`the plane, which pointer contains the address of the
`·lips/Kluwer textbook, the video decoder of the CD-I
`start of the PCL structure of the first free fragment Fl.
`player can be configured by means of entries in a Line
`The pointer PCL-NXT of each fragment is then set to
`Control Table to decode data from any memory loca-
`point to the PCL of the next free fragment in turn, until 40 tion in order to generate a given line of displayed image.
`The application module needs in any case to set up the
`all fragments have been linked. The last free fragment
`F12 has a null pointer '0' in its fleld PCL_NXT. The
`LCT to account for the location of the image buffer,
`extra fleld FRAG-PREV is used to link every free
`and this can now be done to account for the location of
`fragment in the reverse order (F12 to Fl). In each part
`each data segment in its respective fragment. Depend-
`of FIG. 8, the pointers PCL_NXT are represented by 45 ing on the image coding employed, each sector can
`define only a few lines of a full screen image, so that in
`arrows above the fragments, while the reverse pointers
`FRAG-PREV are represented by arrows below the
`a practical embodiment, some tens of sectors are likely
`to be used for one image flle.
`fragments.
`810: Control returns to the application module, which
`Now, for the sample state of the memory reached so
`makes no direct calls to the CDRTOS memory man- SO far at point (B) in the flow chart of FIG. 6, the partition-
`formatting with
`regular
`ing of memory and
`ager 210 thereafter.
`The operation of the application module continues
`PCL+structures might appear to cause excessive com-
`until a point where it is desired to play (for example) a
`plication compared with the conventional memory
`real-time flle containing four sectors of image data. At management operations. However, as more and more
`706 the application module calls function FRAG_ ss flles are read an discarded or kept after playing, the
`problem of memory fragmentation which besets con-
`GRAB of the fragmented memory manager FRAGM,
`ventional systems will never materialise.
`passing the number of sector buffers required as a pa-
`rameter NSECT=4. FRAGM allocates the fust four
`Consider the situation at point (C) in FIGS. 6 and 8,
`free fragments Fl to F4 simply by manipulation of the
`after many real-time ftles have been played and dis-
`pointers as follows, in accordance with the steps 60 carded. At this point, four sectors Fl to