package Ġcom . so y wiz . kor io . compression . util Ċ Ċ import Ġcom . so y wiz . k mem .* Ċ import Ġcom . so y wiz . kor io . experimental .* Ċ Ċ @ Use Experimental ( K or io Experimental Api :: class ) Ċ internal Ġclass ĠH uff man Tree Ġ{ Ċ ĉ comp anion Ġobject Ġ{ Ċĉ ĉ private Ġconst Ġval ĠINVALID _ VALUE Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠIN COMPLETE _ VALUE Ġ= Ġ- 2 Ċĉ ĉ private Ġconst Ġval ĠNIL Ġ= Ġ 1 0 2 3 Ċĉ ĉ private Ġconst Ġval ĠMAX _ LEN Ġ= Ġ 1 6 Ċĉ ĉ private Ġconst Ġval ĠMAX _ CODES Ġ= Ġ 2 8 8 ĊĊĠĠĠĠĠĠĠ Ġ// private Ġconst Ġval ĠENABLE _ EXPERIMENT AL _ FAST _ READ Ġ= Ġfalse Ċĉ ĉ private Ġconst Ġval ĠENABLE _ EXPERIMENT AL _ FAST _ READ Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠENABLE _ EXPERIMENT AL _ FAST _ READ _ V 2 Ġ= Ġtrue Ċĉ ĉ // private Ġconst Ġval ĠENABLE _ EXPERIMENT AL _ FAST _ READ Ġ= Ġfalse ĊĊĠĠĠĠĠĠĠ Ġ// private Ġconst Ġval ĠFAST _ BITS Ġ= Ġ 9 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠFAST _ BITS Ġ= Ġ 1 0 ĊĠĠĠĠĠĠĠ Ġ// private Ġconst Ġval ĠFAST _ BITS Ġ= Ġ 1 1 ĊĠĠĠĠĠĠĠ Ġ// private Ġconst Ġval ĠFAST _ BITS Ġ= Ġ 1 2 ĊĠĠĠĠĠĠĠ Ġ// private Ġconst Ġval ĠFAST _ BITS Ġ= Ġ 1 4 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// private Ġval Ġdata Ġ= ĠInt Array ( 3 Ġ* Ġ 1 0 2 4 ) ĊĊĠĠĠ Ġprivate Ġval Ġvalue Ġ= ĠInt Array ( 1 0 2 4 ) Ċ ĉ private Ġval Ġleft Ġ= ĠInt Array ( 1 0 2 4 ) Ċ ĉ private Ġval Ġright Ġ= ĠInt Array ( 1 0 2 4 ) ĊĊ ĉ private Ġvar Ġnode Offset Ġ= Ġ 0 Ċ ĉ private Ġvar Ġroot : ĠInt Ġ= ĠNIL Ċ ĉ private Ġvar Ġn codes : ĠInt Ġ= Ġ 0 ĊĊ ĉ // ĠLow Ġhalf - word Ġcontains Ġthe Ġvalue , ĠHigh Ġhalf - word Ġcontains Ġthe Ġlen Ċ ĉ val ĠFAST _ INFO Ġ= ĠInt Array ( 1 Ġshl ĠFAST _ BITS ) Ġ{ ĠINVALID _ VALUE Ġ} ĊĠĠĠ Ġval ĠFAST _ NODE Ġ= ĠInt Array ( 1 Ġshl ĠFAST _ BITS ) Ġ{ Ġ 0 Ġ} ĊĊĠĠĠ Ġ// var Ġfast Read Count Ġ= Ġ 0 ĊĠĠĠ Ġ// var Ġslow Read Count Ġ= Ġ 0 ĊĊ ĉ fun Ġread ( reader : ĠBit Reader ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( ENABLE _ EXPERIMENT AL _ FAST _ READ ) Ġreader . ensure Bits ( FAST _ BITS ) ĊĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġthis . root ĊĠĠĠĠĠĠĠ Ġif Ġ( ENABLE _ EXPERIMENT AL _ FAST _ READ Ġ&& Ġreader . bits available Ġ>= ĠFAST _ BITS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println ("${ reader . bits available } Ġ>= Ġ$ FAST _ BITS ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbits Ġ= Ġreader . peek Bits ( FAST _ BITS ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġraw Ġ= ĠFAST _ INFO [ bits ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġraw . to Short (). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġraw Ġshr Ġ 1 6 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( len Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" BITS 1 [ raw =${ raw . hex } ]: Ġlen =$ len , Ġvalue =$ value ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreader . skip Bits ( len ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== ĠIN COMPLETE _ VALUE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= ĠFAST _ NODE [ bits ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// fast Read Count ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ċĉ ĉ do Ġ{ Ċĉĉ ĉ node Ġ= Ġif Ġ( reader . s read Bit ()) Ġnode . right Ġelse Ġnode . left Ċĉ ĉ } Ġwhile Ġ( node Ġ!= ĠNIL Ġ&& Ġnode . value Ġ== ĠINVALID _ VALUE ) Ċĉ ĉ // println (" BITS 2 : Ġ${ node . value }") ĊĠĠĠĠĠĠĠ Ġ// slow Read Count ++ Ċĉ ĉ return Ġnode . value Ċ ĉ } ĊĊ ĉ private Ġfun Ġreset Alloc () Ġ{ Ċĉ ĉ node Offset Ġ= Ġ 0 Ċ ĉ } ĊĊ ĉ private Ġfun Ġalloc ( value : ĠInt , Ġleft : ĠInt , Ġright : ĠInt ): ĠInt Ġ{ Ċĉ ĉ return Ġ( node Offset ++ ). apply Ġ{ Ċĉĉ ĉ // this @ H uff man Tree . data [ 0 Ġ+ Ġthis ] Ġ= Ġvalue Ċĉĉ ĉ // this @ H uff man Tree . data [ 1 0 2 4 Ġ+ Ġthis ] Ġ= Ġleft Ċĉĉ ĉ // this @ H uff man Tree . data [ 2 0 4 8 Ġ+ Ġthis ] Ġ= Ġright ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ H uff man Tree . value [ this ] Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ H uff man Tree . left [ this ] Ġ= Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis @ H uff man Tree . right [ this ] Ġ= Ġright Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ// private Ġinline Ġval ĠInt . value Ġget () Ġ= Ġthis @ H uff man Tree . data [ 0 Ġ+ Ġthis ] ĊĠĠĠ Ġ// private Ġinline Ġval ĠInt . left Ġget () Ġ= Ġthis @ H uff man Tree . data [ 1 0 2 4 Ġ+ Ġthis ] ĊĠĠĠ Ġ// private Ġinline Ġval ĠInt . right Ġget () Ġ= Ġthis @ H uff man Tree . data [ 2 0 4 8 Ġ+ Ġthis ] ĊĊĠĠĠ Ġprivate Ġinline Ġval ĠInt . value Ġget () Ġ= Ġthis @ H uff man Tree . value [ this ] ĊĠĠĠ Ġprivate Ġinline Ġval ĠInt . left Ġget () Ġ= Ġthis @ H uff man Tree . left [ this ] ĊĠĠĠ Ġprivate Ġinline Ġval ĠInt . right Ġget () Ġ= Ġthis @ H uff man Tree . right [ this ] ĊĊĠĠĠ Ġprivate Ġfun Ġalloc Leaf ( value : ĠInt ): ĠInt Ġ= Ġalloc ( value , ĠNIL , ĠNIL ) Ċ ĉ private Ġfun Ġalloc Node ( left : ĠInt , Ġright : ĠInt ): ĠInt Ġ= Ġalloc ( INVALID _ VALUE , Ġleft , Ġright ) ĊĊ ĉ private Ġval ĠCOUNT S Ġ= ĠInt Array ( MAX _ LEN Ġ+ Ġ 1 ) Ċ ĉ private Ġval ĠOFFSET S Ġ= ĠInt Array ( MAX _ LEN Ġ+ Ġ 1 ) Ċ ĉ private Ġval ĠCO FF SET Ġ= ĠInt Array ( MAX _ LEN Ġ+ Ġ 1 ) Ċ ĉ private Ġval ĠCODE S Ġ= ĠInt Array ( MAX _ CODES ) ĊĊĠĠĠ Ġfun Ġfrom Lengths ( code Lengths : ĠInt Array , Ġstart : ĠInt Ġ= Ġ 0 , Ġend : ĠInt Ġ= Ġcode Lengths . size ): ĠH uff man Tree Ġ{ ĊĠĠĠĠĠĠĠ Ġset From Lengths ( code Lengths , Ġstart , Ġend ) ĊĠĠĠĠĠĠĠ Ġreturn Ġthis ĊĠĠĠ Ġ} ĊĊ ĉ fun Ġset From Lengths ( code Lengths : ĠInt Array , Ġstart : ĠInt Ġ= Ġ 0 , Ġend : ĠInt Ġ= Ġcode Lengths . size ) Ġ{ Ċĉ ĉ var Ġold Offset Ġ= Ġ 0 Ċĉ ĉ var Ġold Count Ġ= Ġ 0 Ċĉ ĉ val Ġn codes Ġ= Ġend Ġ- Ġstart ĊĊĠĠĠĠĠĠĠ Ġ// println (" fast Read Count =$ fast Read Count , Ġslow Read Count =$ slow Read Count ") ĊĠĠĠĠĠĠĠ Ġ// fast Read Count Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// slow Read Count Ġ= Ġ 0 ĊĊĉ ĉ reset Alloc () ĊĊĉ ĉ COUNT S . fill ( 0 ) ĊĊĉ ĉ // ĠCompute Ġthe Ġcount Ġof Ġcodes Ġper Ġlength Ċĉ ĉ for Ġ( n Ġin Ġstart Ġuntil Ġend ) Ġ{ Ċĉĉ ĉ val Ġcode Len Ġ= Ġcode Lengths [ n ] Ċĉĉ ĉ if Ġ( code Len Ġ! in Ġ 0 .. MAX _ LEN ) Ġerror (" Invalid ĠH uff man Tree . code Lengths Ġ$ code Len ") Ċĉĉ ĉ COUNT S [ code Len ] ++ Ċĉ ĉ } ĊĊĉ ĉ // ĠCompute Ġthe Ġdis position Ġusing Ġthe Ġcounts Ġper Ġlength Ċĉ ĉ var Ġcurrent Offset Ġ= Ġ 0 Ċĉ ĉ for Ġ( n Ġin Ġ 0 Ġuntil ĠMAX _ LEN ) Ġ{ Ċĉĉ ĉ val Ġcount Ġ= ĠCOUNT S [ n ] Ċĉĉ ĉ OFFSET S [ n ] Ġ= Ġcurrent Offset Ċĉĉ ĉ CO FF SET [ n ] Ġ= Ġcurrent Offset Ċĉĉ ĉ current Offset Ġ+= Ġcount Ċĉ ĉ } ĊĊĉ ĉ // ĠPlace Ġelements Ġin Ġthe Ġcomputed Ġdis position Ċĉ ĉ for Ġ( n Ġin Ġstart Ġuntil Ġend ) Ġ{ Ċĉĉ ĉ val Ġcode Len Ġ= Ġcode Lengths [ n ] Ċĉĉ ĉ CODES [ CO FF SET [ code Len ] ++] Ġ= Ġn Ġ- Ġstart Ċĉ ĉ } ĊĊĉ ĉ for Ġ( i Ġin ĠMAX _ LEN Ġdown To Ġ 1 ) Ġ{ Ċĉĉ ĉ val Ġnew Offset Ġ= Ġnode Offset ĊĊĉĉ ĉ val ĠOFFSET Ġ= ĠOFFSET S [ i ] Ċĉĉ ĉ val ĠSIZE Ġ= ĠCOUNT S [ i ] Ċĉĉ ĉ for Ġ( j Ġin Ġ 0 Ġuntil ĠSIZE ) Ġalloc Leaf ( CODES [ OFFSET Ġ+ Ġj ]) Ċĉĉ ĉ for Ġ( j Ġin Ġ 0 Ġuntil Ġold Count Ġstep Ġ 2 ) Ġalloc Node ( old Offset Ġ+ Ġj , Ġold Offset Ġ+ Ġj Ġ+ Ġ 1 ) ĊĊĉĉ ĉ old Offset Ġ= Ġnew Offset Ċĉĉ ĉ old Count Ġ= ĠSIZE Ġ+ Ġold Count Ġ/ Ġ 2 Ċĉĉ ĉ if Ġ( old Count Ġ>= Ġ 2 Ġ&& Ġold Count Ġ% Ġ 2 Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġerror (" This Ġcanonical Ġcode Ġdoes Ġnot Ġrepresent Ġa ĠH uff man Ġcode Ġtree : Ġ$ old Count ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ċĉ ĉ } Ċĉ ĉ if Ġ( old Count Ġ!= Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġerror (" This Ġcanonical Ġcode Ġdoes Ġnot Ġrepresent Ġa ĠH uff man Ġcode Ġtree ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĉ ĉ this . root Ġ= Ġalloc Node ( node Offset Ġ- Ġ 2 , Ġnode Offset Ġ- Ġ 1 ) Ċĉ ĉ this . n codes Ġ= Ġn codes ĊĊĉ ĉ if Ġ( ENABLE _ EXPERIMENT AL _ FAST _ READ ) Ġ{ Ċĉĉ ĉ compute Fast Lookup () Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġ// Ġ@ TODO : ĠOpt imize Ġthis ĊĠĠĠ Ġprivate Ġfun Ġcompute Fast Lookup () Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( ENABLE _ EXPERIMENT AL _ FAST _ READ _ V 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFAST _ INFO . fill ( INVALID _ VALUE ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcompute Encoded Values ( root , Ġ 0 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" compute Encoded Values : Ġ" Ġ+ Ġcompute Encoded Values ( root , Ġ 0 , Ġ 0 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" FAST _ INFO . size =${ FAST _ INFO . size }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( value Ġin ĠFAST _ INFO . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġthis . root ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbit count Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġif Ġ( value . extract Bool ( bit count ++ )) Ġnode . right Ġelse Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( node Ġ!= ĠNIL Ġ&& Ġnode . value Ġ== ĠINVALID _ VALUE ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFAST _ INFO [ value ] Ġ= Ġif Ġ( bit count Ġ> ĠFAST _ BITS ) Ġ- 1 Ġelse Ġnode . value Ġor Ġ( bit count Ġshl Ġ 1 6 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊ ĉ private Ġfun Ġcompute Encoded Values ( node : ĠInt , Ġencoded : ĠInt , Ġencoded Bits : ĠInt ) Ġ{ Ċĉ ĉ if Ġ( node . value Ġ== ĠINVALID _ VALUE ) Ġ{ ĊĉĉĠĠĠ Ġif Ġ( encoded Bits Ġ< ĠFAST _ BITS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcompute Encoded Values ( node . left , Ġencoded , Ġencoded Bits Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcompute Encoded Values ( node . right , Ġencoded Ġor Ġ( 1 Ġshl Ġencoded Bits ), Ġencoded Bits Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwrite Variants ( encoded , Ġencoded Bits , Ġnode , ĠIN COMPLETE _ VALUE ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ċĉ ĉ } Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwrite Variants ( encoded , Ġencoded Bits , Ġnode , Ġnode . value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// println (" encoded =$ encoded , Ġencoded Bits =$ encoded Bits , Ġn value =$ n value , Ġrange Count =$ range Count ") Ċĉ ĉ } Ċ ĉ } ĊĊĠĠĠ Ġprivate Ġfun Ġwrite Variants ( encoded : ĠInt , Ġencoded Bits : ĠInt , Ġnode : ĠInt , Ġn value : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġencoded Info Ġ= Ġ( n value Ġand Ġ 0 xFFFF ) Ġor Ġ( encoded Bits Ġshl Ġ 1 6 ) ĊĠĠĠĠĠĠĠ Ġval Ġrange Count Ġ= Ġ 1 Ġshl Ġ( FAST _ BITS Ġ- Ġencoded Bits ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( n Ġin Ġ 0 Ġuntil Ġrange Count ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġencoded Ġor Ġ( n Ġshl Ġencoded Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFAST _ INFO [ i ] Ġ= Ġencoded Info ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFAST _ NODE [ i ] Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ