|||H|
`
`US00?3'!8992B2
`
`.12; United States Patent
`Fallon
`
`(10) Patent No.:
`(45; Date of Patent:
`
`US 7,378,992 B2
`*May 27, 2008
`
`(54) CTONTENIF INDEPENDENT DATA
`COMPRESSION METHOD AND SYSTEM
`
`(56)
`
`References Cited
`1
`I.l.S. PA]‘]7.NT I)(}C.'.UM|ZN'l’S
`
`1.75)
`
`lL1vc:11ml':
`
`James J. Falloll, _.-\m1L1r11~:. NY (US)
`
`(73) Assignee: Realtime Data LLC‘. New York. NY
`(US)
`
`( “’
`
`) Nulice:
`
`Stlbjecl In any disclaimer. the term 0111115
`palcnl is exlcnded or adjnslcd under 35
`U.S.(T. 1540: J bv 0 days.
`
`This patent is subject to a terminal dis-
`C-lflinjer‘
`
`(21)
`
`:\pp1.NcI.: m4no,533
`
`(22) Filed:
`
`Apr. 3, 21106
`
`['55)
`
`prim. publication Data
`
`4.303.775 A
`-l.394.'I"’.I‘«1 A
`4_574.351 A
`-1,593.32-1 A
`4.582.150 A
`4.730.343 A
`
`H3195“ widcrgmn at “L
`T"l9{\'3- Widergren cl al_
`3..-[935 Dang ¢-.1
`;1|_
`6-'l‘)Hfi Dhkubo el al.
`T'|9E€7 Maihcs el al.
`351933 Maufriaken
`
`‘C“'“i"“"‘”
`l3'('}R[£I(iN PA'l‘l<‘.N'1' D(}C.‘UMJ-7.N‘l'S
`_
`
`[C‘cmli:1ued1
`OTI HER 1-‘Ul3L[(‘_/\'l‘IONS
`
`“()pe|'ating System Plalforin Absuacljon Med1od“. IBM Technical
`lhsclosure Bulletin. Feb. 1995. ml. 38, Issue No. 2. pp. 343-344
`
`US 200610181-142 Al
`
`Aug. 17. 200:.
`
`Itlmlinlledl
`
`R°‘“'°d “'5' ’‘*’1’"‘'‘‘'‘‘‘''‘ D“
`(63) Contimlatioil ofapplicaliou N0. 101668.168. filed on
`Sep. 22. 2003, now Pat. No. 7,161,506, whicll is a
`CIJl'1li.!11.l[lI10l1 L11‘ zlpplicalioll Nu. 101016.355. filed on
`0.;-L 29_ 3o01_ now pm‘ No_ 5_524_7(,1‘ \.,],i,_-11 is 3
`ggmimgaij.;.n-jn-pa;-1 nj’ ;4pp]i¢alim1 Nu (jt),»‘705‘446_
`filed on Nov. 3. 2000. now Pill. Na 6.309.424. which
`15; 3 comimmt-jm] of appgicatim No_ (}¢_),Q 1{)‘491_ med
`an [}.-_sc_ 1], 1998, new Pap N0, fi.__195,024‘
`
`(51)
`
`Int. Cl.
`12006.01 1
`INIJM 7/34
`(52) U.Si. (fl.
`.......................... ..
`34135.1: 3-JUGS: 341167:
`3.1.1337
`341x50.
`3-1151.67.75.79
`See application file for complete Search liismry.
`
`(53) Field nf Classification Searth
`
`& Gray LI .1’
`
`(57)
`
`ABSTRACT
`
`Systems and metlmds for pmviding fast and ellicient dam
`CI.‘IflJpI'l3S5iL‘Il1 using a conibiiiation of content indcpcndcsll
`dam C'~"7'PT°=“‘i‘-"1 and 90111911‘ d*3P*3fl‘-‘"3111 dam '3'~‘mP"°‘~“‘i0“v
`In one uspecl, -.1 mellmcl for emiipressing dam cmnprisnzs the
`steps 01": analyzing a data block ofan input data stream to
`id:-.‘11li£'y ‘.1 data [ype of 1116 data block. the input data slrcarn
`comprising a plurality of disparate d:-1111 types: pcrlhrrning
`cmiteul dependciil data cmiipressiun on the dam block 11111::
`data we 01' the data block is ideniificd: perlbrming cnnlenl
`indcpcndenl data I'.'-OITlpl'I.‘SSiI.1ll on the data block. ifthe data
`‘NP?-‘ OT 113° 43111 block is 1101 identified-
`
`45 Claims, 34 Drawing Sheets
`
`DA TA STREAM
`
` BUFFER!
`ENCODER E1
`
`COUNTER 1
`3UF[:ER{
`I CQUNTER 2 I
`BUFFFJ
`=
`COUNTER 3
`
`1
`
`ENCODER E2
`
` DATA INPUT
`
`3'-09"
`DATA
`ENCODER E3
`coum-ran
`BUFFER I
`
`
`
`ENCODED DATA
`STREAM W1’
`DESCRIPTOR
`COMPRESSION
`COM|;§E§S-IUN
`RATIO
`DETERMINATION!
`C{]MpARl3DN
`DE5CRiPTiON
`
`
`
`
`
`
`
`
`
`
`
`BUFFER}
`ENCODER En
`
`
`
`COUNTER n
`
`30
`40
`
`Oracle 1001
`
`Oracle 1001
`
`

`
`US 7,378,992 B2
`Page 2
`
`U5’ p_,q1TE_1~..1T DOCUMENTS
`
`4.804.959 A
`4.870.415 A
`4.872.009 A
`4.876.541 A
`4.888.812 A
`4.906.995 A
`4.929.945 A
`4.965.675 A
`4.988.998 A
`5.028.932 A
`5.945.848 A
`5.045.852 A
`5.046.027 A
`5.049.881 A
`5.091.782 A
`5.097.261 A
`5.113.522 A
`5.121.342 A
`5.150.430 A
`5.159.336 A
`5.175.543 A
`5.179.651 A
`5.187.793 .—'\
`5.191.431 A
`5.204.756 A
`5.209.320 A
`5.212.742 A
`5.226.176 A
`5.227.893 A
`5.231-492' A
`5.237.461) A
`5.237.675 A
`5.243.341 A
`5.243.348 A
`5.247.638 A
`5.247.646 A
`5.263.168 A
`5.270.832 A
`5.287.420 A
`5.293.379 A
`5.7-07.497 A
`5.509.555 A
`5.355.498 A
`5.357.614 A
`5.379.036 A
`5.379.757 A
`5.381.145 A.
`5.394.534 A
`5.395.333 A
`5.400.401 A
`5.403.639 A
`5.406.:-‘.78 A
`5.406.279 A
`5.412.384 A
`5.-114.850 A
`5.420.639 A
`5.434.983 A
`5.-152.387 A
`5.461.679 A
`5.467.087 A
`5.471.206 A
`5.479.587 A
`5.483.470 A
`5.486.826 A
`5.495.344 A
`5.506.544 A
`5.506.372 A
`5.530.845 A
`5.533.051 A
`5.535.356 A
`5.537.658 A
`
`
`
`11989 Makansi c1 :1].
`931989 Van Maren etalv
`10.11989 'l'sukiy8n121El 31.
`1011989 Slorcr
`1211989 Diana et :1].
`3.-"1990
`Swa|'_'u9CI1'1
`5-"1993 O'Brien 9131-
`10-‘I990 Hori 131 111.
`171991 O'Brien
`7-‘I991 Huang
`9-‘I991 Fnscenda
`9.11991 Milchell el :11.
`91199]
`”1’a:1fl’c<.~1 :11.
`91991 Gibson :1 al.
`11992 Knmse at al.
`I1.-‘I992 1_:u1gdnn..1r.c1a1.
`531992 I)inwic1die..1r.e1a1.
`611992 Szymborskj
`971992 Chu
`10-"1992 Rabin at n].
`1231991 L381‘!
`:11.
`1.199} Tunifc 1:1‘
`2-“I993 K1ei11'1e1 al.
`311993 Hasegawn e1 :11.
`4.-1995 (‘hevion c1 :11.
`5-‘I993 Hiynnm e1 :11.
`5.-“I993 Normjle e1 :11.
`7-‘I993 Weslaway 9131-
`771993 1311
`711993 Dansi 91 =11.
`8.11993 M11161 ct :1].
`8.11993 1-Iannon. Jr.
`9.11993 Seroussi e1 :11.
`91199} Jackson
`971993 0‘Brie1'1c1'al.
`9.11993 Ostcrlund c1 :11.
`1131993 Tums el al.
`1231993 Balkanski e1 :11.
`2-‘I994 Bnnetl
`391994 Carr
`4.11994 Feigenbmlm e1 :1].
`51994 Akinsel al.
`I0-"1994 Pmvincs cl
`:1].
`1071994 Pat1'is:m1e1.1l.
`11199.5 Slater
`1.-"1995 Hiyama el a].
`171995 Allen ctal.
`2.11995 Kulnkowski e1 :11.
`311995 G-117913
`3.11995 Wasilewski 21 ul.
`4-‘I995 Belsan -4 a|-
`4.11995 Gr.-tybill c1 :11.
`411995 Anderson c1'a1.
`57199.5 Chimg el :1].
`5.1995 Whiting.
`5-‘I995 Perkins
`7-"1995 ‘I"r!=50 El 41-
`9-1995 DiI?t1'¢iC0
`111.4995 516:-mile eta].
`1151995 Chu
`1161995 Allen at al.
`1231995 cmnpbell c1 a1.
`1.11995 Alur-*1 41-
`111996 Rcmillard
`371995 -'E'Ch3I1BEt 31-
`411996 R-'40
`471996 Mahler
`671996 Hia.1.l
`731996 James
`711996 Kim ctal.
`711996 Bnkkectul.
`
`. 710163
`
`5.557.551 A
`5.557.668 A
`5.557.749 A
`5.561.824 A
`5.563.961 A
`5.574.952 A
`5574.953 A
`5.583.500 A
`5.590.306 A
`5.596.674 A
`5.504.324 A
`5.606.706 A
`5.611.024 A
`5.612.783 A
`5.131 3,1159 A
`5_515_(11',1 A
`5‘5;1_1‘gp_{1 A
`5_(._13,fi13 A
`51.33.70; A
`51527534 A
`5.627.995 A
`5.629.732 A
`5.630.092 A
`5..~335_a31 A
`5.635.932 A
`5‘53s_49s A
`3.549.153 A
`5.642.506 A
`5.549_1}3;J A
`5.652.795 A
`5.652.357 A
`5.652.917 A
`3.1154303 A
`5_555_]33 A
`5.555_55u A
`5.668.737 A
`5.671.389 A
`5.575_333 A
`533351915 A
`mg-41151:) A
`5.696.927 A
`5.703.793 A
`5_715_477 A
`5.117.393 A
`5.717.394 A
`5_-,=19_s52 A
`5.721.958 A
`5.724.475 A
`5_7-,zg_,3gs A
`5343,9114 A
`5.757.352 A
`5_771_3.4o A
`5.773.411 A
`53313115? A
`5.784.572 A
`5.787.487 A
`5.795.854 A
`5.799.110 A
`5.805.932 A
`5.808.660 A
`5__g1;1g_175 A
`5.809.337 A
`5.s1_1__'739 A
`5.g13_353 A
`5.818.369 A
`5.818.531) A
`5.819.215 A
`5.825.424 A
`5.825.330 A
`5.832.037 A
`5.332.126 A
`5335-003 -'\
`5.838.996 A
`
`9-"1996 Cmfl
`9.-‘I996 Brady
`971996 Norris
`11171996 Carreim cl :1].
`10-1996 Rynderman el al.
`ll-"1996 Brady (:1 211.
`1111996
`R1151 c1.-11.
`1211996 Allen 1:131.
`131996 Walunahe el al.
`1-"1997 Bhandari :1 nl.
`2.499? Chui at :1].
`2r'1997 'l'.1.ka.1no1u cf :11.
`3.199? Campbell et :11.
`3.11997 Stone
`37199‘: waiku
`3.-"1997 Cl-mi at al.
`4.-"199:-' Ryndurm,-1n at :11.
`4..-"1997 Kim e1;11.
`.1.-"1997 mkke en :11.
`5.199‘;
`("frail
`57199? M1113! c1-:11.
`5-"1997 Mosktlwitzeinl.
`54997 Carreino el al.
`57199? Fay 1:131.
`65199? Shinagawa elnl.
`15.-1997 Tyier e131,
`5-"1997 U](,ay1|.rr1.'1 el al.
`671997 Lee
`77199? Bu:-1‘.e|a_I.
`7-1997 Dillon e1 :1].
`771997 Shiruui e1 :11.
`7.71991 Mallpin e1 3].
`3.-1997 c1.u1;,11
`3.11997 Kikinis
`9.11997 Mognl etul.
`9.-‘I997
`‘Her
`9..-"1997 Saliba
`111.-"199? Bonnier et 31.
`]]r1997 Bakhmulsky
`131997 Kama
`1291997 Maclmnnld :1 al.
`12.41997 wise et al.
`371993 Kikjnis
`2.71998 Nakano ct a].
`271998 Schwart-1' at at.
`271993 Lee 61:11,
`271993 Kjkinis
`3.-1993 Kin.-Ien
`3:15-gs
`Iirannszek (:1 a1.
`5.-1993 H1,|n,1'1g .31 :11.
`S-‘I998 Kericevic e1 :11.
`15.1998 ‘.~.Ia1m7A-110 at a],
`7-"1998 D:-Moss e1 :11.
`77199;:
`‘1mue e1a|_
`75-1993
`1{os1oke1-e1- a1.
`'1'-‘"1998 Hashimoto E1111.
`8.11998 Callahan
`871998
`Israclsen 6131.
`9.-‘"1998 Kawashima -:1 al.
`9.-"1998
`Scl’-cine ct 21.1.
`9..'199s Yajima
`9-‘"1998 Haxuzal-11:1 a].
`9.-"1998 Diaz e1 11].
`1o..'199s Langley
`10.-"1991: Wilhers .................... .. 341.407
`1n.-1998 Czmfield e1 :11.
`I0.-"I998 Dubson el al.
`10.-“I998 Canfielrl e1 :11.
`11131998 Kopf
`II.-1998 Park
`ll-‘"1998 Tanakil
`WI995‘
`535-°h
`1151998 detarmo
`
`3'15.»3-111
`
`341"“
`
`

`
`5.339.199 A
`5.341.979 A
`5.347.752 A
`5.351.324 A
`5.351.929 A
`5.354.342 A
`5.357.157 A
`5.357.592 A
`S.S’1'0.0_'15 A
`5.379.937 A
`5.372.539 A
`5.333.975 A
`5.335.555 A
`5.339.951 A
`S.915,(1'I9 A
`5.917433 A
`5.920.325 A
`5.935.515 A
`5.949.355 A
`5.955.975 A
`5.959.455 A
`5.954.342 A
`5.953.149 A
`5.973.539 A *
`5.974.235 A
`5.974.471 A
`5.9'1’8.-433 A
`5.932.723 A
`5.991.515 A
`5.995.033 A
`5.999.099 A
`5.992.411 A
`5.993.115 A
`5.093.743 A
`5.911.991 A
`5.914.594 A
`5.925.217 A
`5.923.725 A
`5.931.939 A
`5.932.143 A
`5.951.393 A
`5.973.232 A
`5.07S.470 A
`5.991.777 A
`5.994.534 A
`5.997.529 A
`5.194.339 A
`5.195.139 A
`5.123.412 A
`5.141.953 A
`5.145.959 A
`5.159.241 111
`5.172.935 Bl
`5.173.331 Bl
`5.132.125 111
`5.192.932 131
`5.195.924 131
`5.195.455 Bl
`5.222.385 Bl
`5.225.922 131
`5.225.557 111
`5.225.749 Bl
`5.253.254 131
`5.272.173 111*
`
`5.272.527 131
`5.272.523 111
`5.232.541 131
`5.393.311 111
`5.399.424 111
`5.317.714 Bl
`5.339.522 131
`5.345.397 131
`
`11.-1993 Wegener
`1111993 5511111115151 51.
`1211993 195595111 5151.
`1.-1999 Ryu 5151.
`111999 3155115151.
`111999 Kajiya 51 :11.
`211999 12551153
`211999 255111 5151.
`361999 Frzmasfiek 12131.
`211999 (“h.-9.1
`211999 12511195 5151.
`311999 35111-5 11151.
`311999 111.151
`3.11999
`13555511
`511999 Von1l1'1u'1.J1'.ela|.
`511999 A5115
`'1'.'1999 Rentschlur at 91.
`311999 'l‘11rb11rg. Jr. et al.
`911999 91511111111515
`911999 1155111
`911999 Adams
`19.1999 ?5ck.-511
`1911999 155115115 5151.
`1011999 11511111 ......................
`1911999 1111111511); 5151.
`1911999 13511
`1111999 Thnrnpsnn. Jr. el 91.
`11.1999 11515119151
`1111999 15115151.
`ll.'1999 Chiu-11710
`1211999 Brady
`12.11999 Dye
`1211999 115515 5151
`1211999 155115115
`1.12999 11115155
`1.-2099 Al1a1*oni::I:1I.
`2.2099 Adiletla
`212999 1115155555
`2.-2999 551155115151.
`252099 97111155
`5.2999 55.1511 5151.
`512999 1111551151 5151.
`5.-"2000 Little 1:1 :11.
`7.12999 51115125151.
`712999 Yahagi 5151.
`312099 1115115151
`32999 Ando
`3.-2999 Wu 5151.
`19.-2099 5111511
`1912999 31511111115511
`11.-2099 Dye
`112991
`31515151
`1.2991
`K115.-1.5111
`1.-2991 Dye
`1.2991
`11515115 5151.
`212991 3111111515151. 51.
`2.-2991
`151155
`2.9.011] Zandi er al.
`4.-"3001 Y9g1:shw1u'
`512091 1151155
`512991
`1915111151115 5151.
`512091
`155
`512991
`5515551155
`312991 555555155511
`51111.
`312991 M555
`312991 Aguilar 51 51.
`32991 (‘hri1111-5555
`1912091 1:5x1515115515151.
`19.12991
`551155
`11.2091 D1:I{‘a.1s1il19 5151.
`1212091
`351155551
`212992 11115111
`
`US 7,378,992 B2
`Page 3
`
`341137
`
`:11.
`
`341.-'37
`
`341-‘I05
`
`351511 ........................ .. 341151
`512902
`5.392.557 112*
`512092 1711555151.
`5.494.931 Bl
`712992
`31155
`5.421.337 131
`32992 11511
`5.434.153 Bl
`312992
`17515115515151.
`5.434.595 131
`3.2992 111111555511
`5.442.559 Bl
`9.2992 'l'99ria.11s
`5.449.532 111
`912992 M51515
`5.452.592 111
`I0-"E0112
`Tc-om.-.171 at
`5.453.509 Bl
`1112992
`1-15111.-11'
`5437.540 111
`1212992
`1155111
`5.439.992 112
`112993 Kubuyushi
`5.513.113 131
`3.2993 125551515151.
`5.529.533 111
`312993 1111515151.
`5.532.121 Bl
`312003 Stewart
`5.539.456 132
`-1.-‘.2993
`351511
`5.542.544 131
`5-‘Z003 Raslmnssen
`5.577.254 B2
`T-"2003 Kilade 1:1 .11.
`5.590.509 Bl
`72093 51111115
`5.591.194 131
`312993
`1115111555111 5151.
`5.594.949 112
`312993
`151155
`5.504.153 131
`3-“"2993 Abrlui.
`5.505.949 132'
`312993 2515511
`5.595.413 111
`312093 Wolfgang
`5.599.223 131
`9.2993 Rail
`5.513.723 131
`9-2993 151155
`5.524.751 112
`1112003 Nelson 91 al.
`5.650.251 B2‘
`1272993
`15111911 5151.
`5.551.339 Bl
`1212993
`11551111
`5.551.345 111
`319.004 Nuiawadi 91' al.
`5304.840 132
`3.2094 Y5111
`5711.799 131
`412994 75111155
`5.717.534 112
`512094 2115115151.
`5.731.314 132
`52994 01111115 5151.
`5.745.232 132
`512094
`551155 5151.
`5.743.457 112
`512994 125515
`5.755.922 112
`1012994 MI.11h1.1ju1naraswathy 5151.
`5.310.434 132
`412995
`5115111155
`5.335.315 112
`412995 51515515151.
`5.335.319 112*
`52095 31151115115111 5151.
`5.909.333 132
`9.2995 Abali ct 51.
`5.944.749 112
`912095
`1.11.-
`7.192.544 Bl
`10.12005 Fallon
`7.130.913 B2
`1-2097
`551155 ....................... ,. 341151
`7.151.595 1121*
`.3.-2907
`‘Dye 5151.
`7.199.234 Bl
`2991.-9931992 A1* 1912991 2551151 51.
`299119932123 A1
`1912991 Kcpecs
`299119952933 Al” 1212991
`351155 5151.
`2992.-9937935 A1
`312992
`Singl-1
`299219191357 A1
`312992 1.151.551 51 51.
`2992.-9194391 A1
`312992 0115
`2992-9125755 A1
`912992
`1-15151.
`200319939575 A1
`$92993
`F151.-11155551551111.
`299319934995 A1
`212993 A5155 5151.
`29939934233 A1
`512093 0115115 51- 51.
`2993-9142374 A1
`712993 55115552
`
`341151
`
`332.1239
`
`719.153
`
`FOREIGN PAT17‘.N'I‘ DOCUMENTS
`
`375124993
`
`15"
`E1’
`F1’
`Lil’
`1“-1‘
`E1’
`5}’
`U’
`E1’
`EP
`GB
`IP
`JP
`.113
`
`0154077
`0135000
`033-"1793
`0405573 A3
`04055573 *3
`0403'30
`0537437
`0595405
`0713751 A3
`0718751 A3
`2152925
`5951939
`9133009
`11149375
`
`“"935
`00035
`0-0033
`1-0001
`—‘'109|
`70903
`3-"1994
`5-0904
`00090
`211997
`1.1935
`2.1994
`7.1997
`511999
`
`

`
`US 7,378,992 B2
`Page 4
`
`W0
`WO
`W0
`W0
`
`W0 941-1273
`W0 9429852
`WU 9502873
`W0 97482 [2
`
`6: I 99-1-
`l.2' I994
`D1995
`I'll I 99'?
`
`DTI-IIER FUBI.ICATlONS
`
`I-TS." Chip Se: _,“FJ.I" Hfglr-Speed Lo.rs.’er.r Darn
`.-I
`Jack Venbmx.
`[lil'£l':'
`'l‘r:I.r1s. On (‘ircuiI.s and Systems lor Video
`('onr,ore.rrio;i
`.
`Technology. vol. 2. No. 4. Dec. I992. pp. 381-391.
`Pen-Shu Yeh. N19 C‘C‘SDS Lr;.v.r!r-rs Dara C‘o;np;'e.r.s'r‘ori Rt-conmu.~n—
`dafia» jbr Spac'e.4;JpIr'n:rz'oiI.r. Chapter I6. Lossless Compression
`I-Iandbook. Elsevier Science (_L'SAl. 2003. pp. 3l1-325.
`Robert 1‘. Rice. Some Pr'rzcrr'm1' Urifvcvrsol Nofrelesr £‘odr'rrg I'er‘k-
`niqrres . Jet Propulsion Laboratory. Pasadena. California. JPL Pub-
`licaunn 79-22. Mar. I5. I979.
`K. Mllrashitn el n|..
`lligh-Speed Statistical Compression using
`Self-organized Rules and Prcdetcrmineul Code '1'.-Ibles. IEEE. [996
`Data Compression conference.
`IBM. Fast Dos Sofi Boot. Feb.
`I83-I86.
`J. Anderson el al. Coder: squeezes color teleconferencing lhrough
`digital telephone lines. Eleeuonics I984. pp. I3-I5.
`Roberl Rice. "Lossless Coding Slamiards For Space Dam S}-Steins".
`IEEE 1058-6393.-'97. pp. 577-535.
`Coene. W et nl. “A linsl Roule For Application ol'R.1le-rlislorlion
`Uptirnal Qurintization in an MPF.(“s Video Encoder" Proceedings of
`Lhe lntrxnaoonnl Conference on Image Processing. US.. New York.
`IEEF. Sep. 16. 1996. pp. 825-828.
`compression".
`video
`and
`Mil|II!a.n.
`Howard,
`"Image
`Compurcrworld, vol. 33. Issue No. 3. Jan. I8. I999, pp. 78.
`
`l. 1994. vol. 31'. Issue 28. pp.
`
`Ju_n.. 25, 2000
`“IBM boosts your mezrnory". Gcek.con1 [online].
`[retrieved on Jul.
`(1. 3007].
`-:URI.‘. 1111p:Nw\W\‘.gee-k.con1."ib.111-
`boosts-your-memory.-'>.
`“IBM Research Breakihrollgh Doubles Computer Memory Capac-
`ity". IBM Press Release [online]. Jun. 26. 2000 [rolzricved on Jul. 6.
`3907].
`<l_.'_RI.:
`I1|1p:.-".-'ww'w-U3.il:Im.co1na'pressius-"erL"pressrelease
`-']653.wss>.
`
`“Sen'erWorks To Deliver IBM‘ 3 Memory expansion Technology in
`e\Iexl-Generation Core Logic for Servers”. Servcrworlrs Press
`Release [on|ine|. Jun. 27. 2000 [rel riewerl on Jul. I4. 3000]. <1 .TRI..:
`hltp:.-'»'\w:w.serve1works.comr'n o\I.'s.-press." D0062‘.-‘ ,hImI:.
`Ahali, I3.. cl‘ al.. "Memory Ijxprmsion Technology (MET) Software
`supporl amt perl'on'nance". IBM iournal of Rese.a.n':h and ‘Develop-
`rnenl. vol. -45. Issue No. 3.. Mar. 2001, pp. 287-3Ul.
`Frana.-rzck. P. A.. at al.. "_-tlgoriljzms and data suucrures for com-
`pressed-:nen1o1'}' machines“. IBM Journal of Research and Devel-
`opmeni. vol. 45. Issue No. 2. Mar. 2001. pp. 245-258.
`Frarlaszek. P. A. el a]_. "{)n interns] organirmion in compressed
`rarldom-access memories". IBM Journal of Research and Develop-
`nrenl. vol. 45. Issue No. 2. Mar. 300]. pp. 259-270.
`Sn1il.l‘I. T.B.. el n.I.. "Memory E!q)a.|1sion Technology (MXTl (‘om-
`pctillvc impact". IBM Journal of Research and Development. V0.
`45. Issue ‘filo. 3. Mar. 2001. pp. 303-309.
`Tremaine. R. 8.. cl al.. “IBM Memory F.xpa.nsion "Technology
`{MX'I'>". IBM Journal of Research and Development. vol. 45. Issue
`No. 2. Mar. 2001. Pp. 2T1—2R5.
`
`“' cited by exzunincr
`
`

`
`U.S. Patent
`
`May 27, 2003
`
`Sheet 1 of 34
`
`US 7,378,992 B2
`
`I I I I
`
`1
`
`I
`f-/
`I
`
`I I
`
`INPUT DATA STREAM
`
`
`
`IDENTIFY INPUT DATA TYPE AND
`GENERATE DATJEIGYIEELIDENTIFICATION
`DATA TYPE
`ID SIGNAL .
`COMPRESS DATA IN ACCORDANCE WITH
`IDENTIFIED DATA TYPE
`
`2
`
`3
`
`I--—
`
`I I I
`
`‘
`
`I I I I I
`
`l—"
`
`COMPRESSED DATA STREAM
`
`RETRIEVE DATA TYPE
`INFORMATION or-' COMPRESSED
`DATA STREAM
`
`WITH IDENTIFIED DATA TYPE
`
`DECOMPRESS DATA IN ACCORDANCE
`
`I I |
`
`|
`
`I I I I I
`
`FIG. ‘I
`
`PRIOR ART
`
`

`
`
`
`lllfilgd‘S'l'l
`
`3
`
`3
`‘
`§00
`
`3
`3
`IN-I
`-°-.
`'~
`‘E
`
`C‘
`U}
`:4la-I
`----l
`99
`
`§WI
`
`‘)
`
`BUFFER!
`
`
`
`
`
`
`ENCODED DATA
`STREAM wz
`
`ENCODER E2
`cgBrF~1ErE:2
`osscmpron
`
`
`DATA
`INPUT
`BUFFER!
`C°MgE.'fi'g5'°”
`COMPRESSION
`BLOCK
`DATA
`DETERMINATION!
`TYPE
`ENCGUER E3
`COUNTER
`BUFFER
`I-«DUNTER 3
`COMPARISON
`DESCRIPTION
`10
`:
`.
`
`
`
`
`
`
`
`
`
`
`
`
`ENCODER E"
`
`BUFFER!
`COUNTER n
`
`
`
` 30
`
`40
`
`FIG. 2
`
`

`
`U.S. Patent
`
`Mav27. 2008
`
`Sheet 3 M34
`
`US 7,378,992 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`
`INPUT DATA STREAM
`
`300
`
`B
`
`COUNT SIZE OF
`DATA BLOCK
`
`302
`
`BUFFER DATA BLOCK
`
`304
`
`COMPRESS DATA
`BLOCK WITH
`ENABLED ENCODERS
`
`05
`
`/3
`
`303
`
`310
`
`312
`
`314
`
`BUFFER ENCODED
`DATA BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`CALCULATE
`COMPRESSION
`RATIOS
`
`COMPARE
`
`THRESHOLD LIMIT
`
`COMPRESSION
`RATIOS WITH
`
`FIG. 3a
`
`

`
`U.S. Patent
`
`May 27,2003
`
`Sheet 4 of 34
`
`US 7,378,992 B2
`
`316
`IS
`
`COMPRESSION
`
`
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`
`GREATER THAN
`THRESHOLD?
`
`
`
`NO
`
`
`
`APPEND NULL
`DESCRIPTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`
`
`
`
`SELECT ENCODED
`DATA BLOCK WITH
`GREATEST
`COMPRESSION RATIO
`
`
`
`
`
`APPEND
`CORRESPONDING
`DESCRIPTOR
`
`
`
`318
`
`320
`
`
`
`
`
` OUTPUT UNENCODED
`DATA BLOCK WITH
`NULL DESCRIPTOR
`
`
`
`OUTPUT ENCODED
`DATA BLOCK WITH
`DESCRIPTOR
`
`
`
`
`
`DATA BLOCKS IN INPUT
`STR EAM?
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT"
`STREAM
`
`330
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`
`
`FIG. 3b
`
`

`
`
`
`
`
`EHZ66‘8L€‘LSnrsJO9mus800:‘:12New1ua;gd-S-Q
`
`EIUFFEFU
`
`COUNTER 1
`DA TA STREAM ENCODER E1
`
`
`ENCODED DATA
`
`STREAM w/
`BUFFER!
`
`ENCODER 52
`COUNTER 2
`aescmpron
`
`COMPHESSHON
`COMPRESSION
`
`DATA
`INPUT
`BUFFER!
`RATIO
`
`
`BLOCK
`DATA
`ENC-QDE 5
`
`coumen
`BUFFER
`R 3
`COUNTER 3
`°'E:I]En';‘|§1':gT{_ifi”’
`
`
`TYPE
`DESCRIPTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`ENCODER En
`
`ENCODER
`DESIR ABILITY
`FACTORS
`
`70
`
`FIGURE OF
`MERIT
`DETERMINATION
`
`80
`
`FIG. 4
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 6 of 34
`
`US 7,378,992 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`B
`
`COUNT SIZE OF
`DATA BLOCK
`
`BUFFER DATA BLOCK
`
`500
`
`502
`
`504
`
`COMPRESS DATA
`BLOCK WITH
`ENABLED ENCODERS
`
`505
`
`508
`
`510
`
`1
`5 3
`
`14
`
`5
`
`516
`
`
`
`
`
`APPEND CORRESPONDING
`DESIRABILITY FACTORS TO
`ENCODED DATA BLOCKS
`
`
`
`
`
`BUFFERENCODEDDATA
`BLOCK OUTPUT
`FROMEACHENCODER
`
`coum SIZE OF
`ENCODED DATA
`
`BLOCKS
`
`CALCULATE
`COMPRESEON
`RATIOS
`
`
`
`COMPARE COMFIRESSION
`RATIOS WITH THRESHOLD
`LIMIT
`
`
`
`FIG. 5a
`
`

`
`U.S. Patent
`
`May 27, 2003
`
`Sheet 7 of 34
`
`US 7,378,992 B2
`
`518
`IS
`
`
`COMPRESSION
`
`RATIO OF AT LEAST ONE
`
`ENCODED DATA BLOCK
`
`G REATER THAN
`
`THRESHOLD?
`
`
`
`
`
`
`
`
`
`
`APPEND NULL
`DESCRIFTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`520
`
`CALCULATE FIGURE OF
`MERIT FOR EACH ENCODED
`DATA BLOCK WHICH EXCEED
`THRESHOLD
`
`
`
`SELECT ENCODED DATA
`BLOCK W!TH GREATEST
`FIGURE OF MERIT
`
`OUTPUT UNENCODED
`DATA BLOCK WITH
`NULL DESCRIPTOR
`
`522
`
`APFEND
`CORRESPONDING
`DESCRIPTOR
`
`
`
`OUTPUT ENCODED
`DATA BLOCK WITH
`DESCRIPTOR
`
`MORE
`DATA BLOCKS IN
`INPUT STREAM?
`
`
`
`
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`
`
`534
`
`RECEIVE NEXT DATA
`
`BLOCK FROM INPUT
`STREAM
`
`
`B
`
`FIG. 5b
`
`

`
`
`
`
`
`
`
`EHZ66'8L€"LSflPEJ"8l°3llS8002‘LE“IVJIIBJIE‘-I'S'f1
`
`BUFFER!
` ENCODER E1
`
`
`DATA STREAM
`COUNTER 1
`ENCODED DATA
`
`STREAM WI
`BUFFER;
`
`DESCRIPTOR
`ENCUDER E2
`COUNTER 2
`
`COMPRESSION
`
`COMPRESSION
`RATIO
`ENCODEF: E3
`BUFFER’
`TYPE
`
`COUNTER 3
`DESCRIPTION
`
`
`
`
`
`D'f.LEk:‘;$f‘5T(;‘:‘N’
`
`
`
`
`
`
`
`INPUT
`DATA
`BUFFER
`
` ENC-ODER En
`COUNTER n
`
`BUFF ER!
`
`
`
`USER-
`SPECIFIED TIME
`
`
`
`
`90
`
`FIG. 6
`
`

`
`U.S. Patent
`
`May 27, 2003
`
`Sheet 9 of 34
`
`US 7,378,992 B2
`
`710
`
`TIME EXPIRED?
`
`
`
`
`NO
`
`No
`
`YES
`
`
`
`
`STOP
`ENCODING
`PROCESS
`
`
`
`712
`ENCODING
`
`COMPLETE?
`
`vas
`
`?00
`
`70
`
`B
`
`INPUT INITIAL
`
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`COUNT 312:: OF
`DATA BLOCK
`
`704
`
`BUFFER DATA BLOCK
`
`705
`
`INITIALIZE TIMER
`
`.303
`
`BEGIN
`COMPRESSING
`DATA BLOCK WITH
`ENCODERS
`
`
`
`
`
`ENCODER WITHIN TIME LIMIT
`
`BUFFER
`Efiggggfigfigfi
`FROM EACH
`
`
`
`718
`BUFFER NCODED
`DATA BLOCK FOR EACH
`ENCODER THAT
`COMPLETED ENCODING
`PROCESS
`
`
`
`720
`
`
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`
`
`722
`
`
`
`CALCULATE
`COMPRESSION
`RATIOS
`
`
`
`
`
`724
`
`COMPARE COMPRESSION
`
`RATIOS WITH THRESHOLD
`LIMIT
`
`
`
`
`
`FIG. 7a
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 10 of 34
`
`US 7,378,992 B2
`
`726
`IS
`
`
`COMPRESSiON
`
`
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`
`
`
`NO
`
`728
`
`730
`
`
`
`APPEND NULL
`DESCRIPTUR TO
`UNENCODED INPUT
`DATA BLOCK
`
`SELECT ENCODED
`DATA BLOCK WITH
`GREATEST
`COMPRESSION RATIO
`
`
`
`
`
`APPEND
`
`CORRESPONDING
`
`DESCRTPTOR
`
`
`
`
`OUTPUT UNENGODED
`OUTPUT ENCQDED
`DATA BLOCK WTTH
`DATA BLOCK WITH
`NULL DESCRIPTOR
`DESCRIPTOR
`
`
`
`
`
`DATA BLOCKS IN INPUT
`
`ST REAM?
`
`
`
`7'40
`
`RECENE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`
`
`TEFEMTNATE DATA
`COMPRESSION
`PROCESS
`
`
`
`
`FIG. 7b
`
`

`
`
`
`10313:]'S'fl
`
`EHZ66'8L€'LS11V51911WW5
`
`
`
` 800:‘LZflaw
`
`
`
`COUNTER n ENCOCIER En UIII
`
`
`
`BUFFER!‘
`
`
`
`USER-
`SPECIFIED TIME
`
`
`
`
`ENCODER
`FIGURE OF
`DESIRABILITY
`MERIT
`FACTORS
`DETERMINATION
`
`
` ?'D
`BC!
`
`
`
`
`
`FIG. 8
`
`
`
`ENCODER E1
`
`
`BUFFER}
`COUNTER 1
`
`DATA STREAM
`
`
`
`
`
`10
`
`
`
`
`
`
`ENCODED DATA
`STREAM WI
`BUFFER!
`DESCFUPTOR
`ENCODER E2
`COUNTER 2
`
`CoM:$EgSlDN
`COM:§$|g5|0N
`BUFFER!
`Igigg
`[NI3BL:Eg:TA
`
`DESCWWON
`DETERMINATION!
`COUNTER 3
`BUFFER
`PROCESSOR!
`ENCODER E3
`COMPARISON
`COUNTER
`
`
`

`
`
`
`
`
`Z8z66‘8L€‘LSnt'E10IImussoon:New1119134'g'{1
`
`
`
`BICI. 2
`BIC 1.n
`are 1.1.
`
`
`DATA STREAM
`
`
`
`
`
`
`BIC 2.1
`
`BIC 2.2 . . .
`
`BIC 2.n
`
`COMPRESSION
`INPUT
`RATIO
`DATA
`DETERMINATION
`BIC 3.2
`are 3,1
`BIC 3.n
`.-‘
`BUFFER
`
`
`COMPARISON
`
`
`DATA
`BLOCK
`COUNTER
`
`
`
`
`
`
`
`
` 2
`BIC m,‘I BIC m.
`BIC m,n
`FIGURE OF
`
`MERIT
`DETERMINATION
`
` COMPRESSION
`ENCODER
`TYPE
`DESIRABILETY
`DESCRIPTION
`FACTORS
`
`
`
`ENCODED DATA
`STREAM WV’
`DESCRIPTOR
`
`FIG. 9
`
`

`
`U.S. Patent
`
`May 27, 2003
`
`Sheet 13 of 34
`
`US 7,378,992 B2
`
`100
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`
`102
`
`B
`
`COUNT SIZE or
`DATA BLOCK
`
`104
`
`BUFFER DATA
`BLOCK
`
`105
`
`INITIALIZE TIMER
`
`‘I08
`
`APPLY INPUT DATA
`BLOCK TO FIRST
`ENCODING STAGE
`IN CASCADED
`
`ENCODER PATHS
`
`
`
`
`APPLY OUTPUT
`
`
`OF COMPLETED
`ENCODING
`
`STAGE TO NEXT
`ENCODING
`
`
`STAGE IN
`
`
`CASCADE PATH
`
`
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM
`COMPLETED
`ENCODING
`STAGE
`
`118
`
`STOP ENCODING
`PROCESS
`
`'
`
`
`
`SELECT BUFFERED OUTPUT OF LAST
`ENCODING STAGE IN ENCODER
`CASCADE THAT COMPLETED ENCODING
`PROCESS WITHIN TIME LIMIT
`
`
`
`
` COUNT SIZE OF
`‘I22
`ENCODED DATA
`BLOCKS
`
` CALCULATE
`COMPRESSION
`RATIOS
`
`124
`
`
`
`
`126
`
`
`
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD
`LIMIT
`
`
`
`
`
`FIG. 103
`
`A
`
`
`
`(110
`
`
`
`TIME EXPIRED?
`
`‘I16
`
`NO
`
`
`
`‘I1 4
`
`YES
`
`N0
`
`COMPLETE’?
`
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 14 of 34
`
`US 7,378,992 B2
`
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`
`
`
`
`APPEND NULL
`
`CALCULATE FIGURE OF
`DESCRIPTOR TO
`MERIT FOR EACH ENCODED
`DATA BLOCK WHICH EXCEED
`UNENCODEO INPUT
`DATA BLOCK
`THRESHOLD
`
`
`
`
`
`134
`
`‘I30
`
`
`
`
`
`
`SELECT ENCOD ED DATA
`BLOCK WITH GREATEST
`
`FIGURE OF MERIT
`
`136
`
`OUTPUT UNENCODED
`DATA BLOCKWITH
`NULL DESCRIPTOR
`
`APPEND
`CORRESPONDING
`DESCRIPTOR
`
`
`
`140
`
`OUTPUT ENCODED
`DATA BLOCK WITH
`DESCRIPTOR
`
`
`
`
`
`
`
`MORE
`DATA BLOCKS IN
`INPUT STREAM?
`
`
`PROCESS
`
`
`
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`144
`
`YES
`
`'3
`
`FIG. 10b
`
`ERMINATE DATA
`COMPRESSION
`
`

`
`
`
`lllalad'S'fl
`
`3
`-33I9
`
`§
`
`U2:1’
`
`E E
`
`9-.La
`«Is
`
`Z8Z66‘8L‘Z'LSH
`
`DA TA WI NULL
`DESCRIPTOR
`
`
`DECODER D1
`
`
`
`
`
`
`DATA STREAM INPUT DATA
`BLOCK BUFFER
`
`DESCRIPTOR
`EXTRACTION
`
`DECODER D2
`
`953093; 93
`
`DECODER Dn
`
`1104
`
`FIG. 11
`
`ourpur DATA
`
`STREAM
`
`
`
`OUTPUT DATA
`BUFFER
`
`

`
`U.S. Patent
`
`May 27. 2008
`
`Sheet 16 of 34
`
`US 7,378,992 B2
`
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`1200
`
`BUFFER DATA BLOCK
`
`1202
`
` EXTRACT DATA
`COMPRESSION TYPE
`DESCRIPTOR
`
`1204
`
`‘I208
`
` IS DATA
`
`COMPRESSION
`TYPE DESCRIPTO
`NULL?
`
`‘I208
`
`
`
`SELECT |'JECODER(S)
`CORRESPONDING TO
`DESCRIPTOR
`
`
`
`
`
`DECODE DATA BLOCK USING
`
`SELECTED DECOOER(S)
`
`RECEIVE NEXT
`DATA BLOCK IN
`INPUT STREAM
`
`
`
`DATA BLOCK
`
`OUTPUT
`UNDECODED
`
`
`
`
`
` MORE DATA
`BLOCKS IN INPUT
`
`STREAM?
`
`
`OUTPUT IJECODED
`DATA BLOCK
`
`
`
`
`
`TERMINATE
`DECODING PROCESS
`
`1218
`
`FIG. 12
`
`

`
`
`
`areZ66‘8L€'Lsotwo1.1wallssuuz‘LEKawwand'S'f1
`
`
`
`
`
`Content Dependent Encoders
`
`Encoder D1
`
`
`
`7320 "”
`
`Encoder D2
`
`Encoder [)3
`
`Encoder Dm
`
`
`
`Dara
`
`Conlent
`
`
`
`Dependent
`D3‘? _
`No
`Content Independent
`
`Reoognrtron
`Encoders
`
`Encoder E1
`
`
`
`Encoder E2
`
`Data;'Fi|e
`Encoder E3
`
`
`Recognition
`
`Liens) or
`
`A|gorithm(s)
` Encoder En
`
`
`
`FIGURE 13A
`
`

`
`1330 ~
`
` Buffer!Counters D1
`
`
`Bufierlcounters D2
`
`
`
`Buffericounters D3
`
`
`
`
`
`(If Required}
`
`
`
`
`
`ZflZ66‘sL£‘LSnrun81uaaus300:'.r.zviewwaned'37]
`
`
`
`
`
`
`
` Bufferlcounters Dm
` Encoded
`Data with
`Determine
`Descriptor
`Append
`Compression
`Compression
`Ralio
`Type
`Descriptor
`
`
`
` Buffer.r‘CoL:nters E1
`Bufferfcounters E2
`
`
` Buffericounters E3 40-» ... Bufferfcounters En
`
`1 350
`
`FIGURE 13B
`
`

`
`US. Patent
`
`May 27. 2008
`
`Sheet 19 of 34
`
`US 7,378,992 B2
`
`
`
`
`
`Receive lnitiai
`Data Block From
`
`Input Data
`Stream
`
`--1400
`
`Count Size of
`Data Block
`
`F‘ 1402
`
`Buffer Data Block --‘1404
`
`
`
`
`
`
`Recognize Data
`Stream Content
`
`?
`
`No—> B
`
`FIGURE MA
`
`Apply Content
`Dependent Data ~1406
`Recognition
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 20 of 34
`
`US 7,378,992 B2
`
`
`
`
`
`Compress Data
`Block with
`
`
`
`Enabled Content
`
`--1410
`
`Independent
`
`
`Encoders
`
`
`
`
`
`
`Buffer Encoded
`Data Block Output
`From Each
`
`Encoder
`
`'--1412
`
`
`Count Size of
`Encoded Data
`~'l474
`
`Blocks
`
`
`
`Calculate
`
`Compression
`Ratio
`
`-1416
`
`
`
`
` Compare
`
`Compression
`Ratios with
`
`~141B
`
`Threshold Limit
`
`FIGURE 14B
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 21 of 34
`
`US 7,378,992 B2
`
`
`
`
`
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`ndependent Threshoi -
`1420 ~
`
`
`
`
`
`Select Encoded
`Data Block with
`Greatest
`
`
`
`Append Nuil
`Descriptor to
`Unencoded input
`Data Block
`
`
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`Output Unencoded
`Data Biock with
`
`Null Descriptor
`
`
`
`
`
`
`More Data
`
`Terminate
`
`
`
`
`
`
`Receive Nexl
`
`Data Block From -
`
`
`Input Stream
`
`Blocks in input
`Data Compression
`Stream
`Process
`
`?
`
`
`Yes
`
`1430
`
`FIGURE 14C
`
`
`
`Compression Ratio
`
`
`
`

`
`U.S. Patent
`
`May 27,2003
`
`Sheet 22 of 34
`
`US 7.378.992 B2
`
`No+ F
`
`
`
`Compression
`Ratio of at Least One
`Encoded Data Block
`Greater Than
`
`
`
`
`
`
`
`Content Dependent
`Threshold
`‘?
`
`
`
`~‘l448
`
`Select Recognized
`1434-» -Data Type!Fi|e or Block
`in List or Algorithm
`
`Select Content
`
`Dependent
`Algorithm{s)
`
`1436 --
`1440 -
`
`1438
`
`Compress Data Block
`with Enabled Content
`
`Dependent Encoder(s)
`
`Buffer Encoded Data
`
`Block From Each
`Encoder
`
`1442 "’
`
`1444 ~
`
`Count Size of Data
`
`Blocks
`Compression Ratio
`
`Calculate
`
`FIGURE 14D
`
`

`
`
`
`
`
`
`
`28Z66‘sL£‘Lsorun:2:raaus300:'.r.zviewwaned'37]
`
`Content Dependent Encoders
`
`
`
`
`Encoder D1
`
`1320 ~
`
`Encoder D2
`
`Encoder D3
`
`
`
` Content
`Dependent
`Encoder DIT1
`Data
`
`
`
`
`Dam
`
`Recognition
`
`
`
` Data!FE|e
`Recognition
`List(s} or
`Algorithm{s)
`
`
`
`
`
`1310
`
`FIGURE 15A
`
`

`
`
`
`1“9Wd‘ST!
`
`E
`-<
`
`SI»)
`6
`
`GO5
`
`an
`S‘
`
`EN
`Sa-
`
`3.
`
`53'
`
`Z8Z66‘8L'E"£.SH
`
`1330 ~
`
`
`Bufferfcounters D1
`
`Compression Ratio
`Bufferlcounters D2
` Content
`
`Above Threshold
`Dependent
`
`Compression
`Threshold
`Test
`
`Bufferlcounters D3
`
`
`
`Encoded
`Data with
`
`
`Compression
`Descriptor
`
`Type
`
`Descriptor
`
`
`
`
`
`Bufferrcounters Dm
`
`s
`1 350
`
`
`Determine
`
`Compression
`Ratio I
`Threshold
`
`Cornression Ratio Below Threshold
`
`
`
`
`Content Independent Encoders
`Encoder E1
` Bufierlcounters E1
`Encoder E2
`Bufferfcounters E2
` Encoder E3
`
`EiufferiCounter5 E3
`
`
`
`
`
`
`
`
`
`
`
`30-
`Encoder En
`Bufferfcounters En
`
`
`FIGURE 15B
`
`

`
`US. Patent
`
`May 27. 2008
`
`Sheet 25 of 34
`
`US 7,378,992 B2
`
`Receive Initial
`
`Data Block From
`
`--1600
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`‘H 1602
`
`Buffer Data Block --1604
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`--1606
`
`Recognize Data
`Stream Content
`
`No—I— B
`
`FIGURE 16A
`
`

`
`US. Patent
`
`May 27, 2008
`
`Sheet 26 of 34
`
`US 7,378,992 B2
`
`B
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`-«16‘i0
`
`Buffer Encoded Data
`
`Biock Output From --1612
`Each Encoder
`
`Count Size of
`Encoded Data Blocks W 161 4
`
`Calculate
`
`Compression
`Ratio
`
`-~ 1616
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`--1618
`
`D
`
`FIGURE 16B
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 27 of 34
`
`US 7,378,992 B2
`
`
`
`
`
`
`Compression Ratio
`of at Least One Encoded Data
`
`
`Block Greater Than Content
`
`Independent Threshotd
`1520 -
`
`
`
`F
`
`
`
`APPGW3 NU"
`Descfipmr to
`Unencoded Input
`Data 3'°°k
`
`Select Encoded
`Date Btock with
`Greatest
` Compression Ratio
`
`
`
`1622 -
`
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`
`
`1624 --
`
`
`
`Output Unencoded
`Data Btock with
`
`Nult Descriptor
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`1626
`
`
`
`
`
`
`
`
`
`
`
`Receive Next
`Data Block From --
`
`
`
`Input Stream
`
`More Data
`
`Terminate
`
`Blocks in Input
`Stre am
`’.>
`
`
`Yes
`
`FIGURE 16C
`
`Data Compression
`Process
`
`1630
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 23 of 34
`
`US 7,378,992 B2
`
`Select Recognized
`1634-» Data Type!FiIe or Block
`in List or Algorithm
`
`1636 -—
`
`Select Content
`
`Dependent
`Algorithm(s)
`
`
`
`Dependent Encoder(s)
`
`Compress Data Block
`1638 —- with Enabled Content
`
`Buffer Encoded Data
`
`1640 ~
`
`Block From Each
`Encoder
`
` Compression
`
`Ratio of at Least
`
`
`One Encoded Data
`
`Block Greater Than
`
`
`
`
`No» B --1648
`
`
`
`1642 w
`
`Count Size of Data
`Blocks
`
`
`
`Content Dependent
`Threshold
`
`1644 ~
`
`Calculate
`.
`.
`Compressnon Ratio
`
`Yes
`it
`
`E
`
`FIGURE 16D
`
`

`
`
`
`Z8z66‘8L£“LSnPE!“52mus30021:-fewnlanzd'31]
`
`
`
`
`
`Content Dependent Encoders
`
`Encoder D1
`139° “-
`Encoder o2
`
`Encoder [)3
`
`A
`
`Dara
`3,
`
`
`
`Content
`
`Dependent!
`mam Data Block
`Independent
`Data
`
`
`Recognition
`Content Independent Encoders
`
`
`
`10
`
`20
`
`1700
`
`Encoder E1
`
`Encoder E2
`
`
`
`B
`Encoder E3
`Data!Fite Type
`
`Recognition and
`
`Estimation Algorithm
`
`or Look-Up Tables
`Encoder En
`
`5
`1710
`
`
`
`FIGURE 17A
`
`

`
`Encoded
`Data with
`
`
`
`Z8z66‘8L£‘LSnrun05:loanssoon:NewJuamd°g'{1
`
`
`
`
`
`
`Bufierfcounters D1
`Bufferfcounters D2
`
`1330-u
`
`
`
`Bufferlcounters D3
`
`
`
`Bufrericounters Drn
`
`
`
`Buffer!Cnunters En
`
`
`
`FIGURE ‘17B
`
`
`
`Compression
`Descriptor
`
`Type
`Descriptor
`
`Bufferfcounters E1
`
`
`1 340
`1350
`
`Bufferfcounters E2
`Buffsrrcounters E3
`
`
`
`Determine
`Compression
`Ratio
`
`(If Required)
`
`
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet .31 of 34
`
`US 7,378,992 B2
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`--1800
`
`Count Size of
`Data Btock
`
`M1802
`
`Buffer Data Block «-1804
`
`Apply Content
`Dependent I
`Independent Data
`Recognition
`
`«-1806
`
`Recognize Data
`_ Stream Content
`
`No—> B
`
`FIGURE 18A
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 32 of 34
`
`US 7.378.992 B2
`
`Estimate Optimum
`Encoder(s) From
`Estimation Algorithms
`
`Compress Data
`Block with Enabled
`Content Independent
`Encoders
`
`Buffer Encoded Data
`Block Output From
`Each Encoder
`
`Count Size of
`
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`FIGURE 18B
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 33 of 34
`
`US 7,378,992 B2
`
`
`
`
`
`
`
`
`
`Compression Ratio
`of at Least One Encoded Data
`
`Block Greater Than Content
`
`Independent Threshol
`1820 -
`
`F
`
`
`
`Select Encoded
`AP|3e’_‘d NU"
`Data Block with
`Descriptor to
`
`Greatest
`Unencclded lnpUt
` 1822 —~-«
`Compression Ratio
`Data 3105"
`
`
`
`
`
`
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`More Data
`
`Terminate
`
`- Data Compression
`Process
`
`Receive Next
`
`Data Block From
`
`Input Stream
`
`
`
`
`
`
`
`
`Blocks in Input
`
`Stream
`'?
`
`
`Yes
`
`1 830
`
`FIGURE 18C
`
`

`
`U.S. Patent
`
`May 27, 2008
`
`Sheet 34 of 34
`
`US 7,378,992 B2
`
`
`Select Recognized
`1838 ~ D ata Type!Fi1e or Block
`in List or Algorithm
`
`
`
`Select or Estimate
`
`1840 —- Content Dependent
`Algorithm(s)
`
`
`
`
`
`
`
`
`Content Dependent
`
`--1850
`
`1842
`
`Compress Data Block
`with Enabled Content
`
`Dependent Encoder(s)
`
`1844 ~
`
`Buffer Encoded Data
`Block From Each
`
`1646 A’
`
`Count Size of Data
`Blocks
`
`1848 ~
`
`Calculate
`.
`.
`Compression RENO
`
`Encoder
`No-1» F Threshold
`
`Ratio of at Least
`
` Compression
`
`One Encoded Data
`Block Greater Than
`
`Yes
`1'
`
`E
`
`FIGURE 18D
`
`

`
`US 1378.992 B2
`
`2
`
`1
`CONTENT INDEPENDENT‘ DATA
`COMPRESSION Ml-ITI [OI] AND SYSTEIVI
`
`CROSS-REFERENCE TO RELATED
`APPI..lC.-’-\T IONS
`
`This application is a (‘ontinuation of U.S. patent appli-
`cation Ser. No. l(lt6(i8.7ti8. filed on Sep. 22. 2003. now US.
`Pa