October 24, 2021, 03:03:38

Author Topic: [bb] Huffman Compression by Murilo [ 1+ years ago ]  (Read 562 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Huffman Compression by Murilo [ 1+ years ago ]
« on: June 29, 2017, 00:28:39 »
Title : Huffman Compression
Author : Murilo
Posted : 1+ years ago

Description : Sorry about the lame example (included in the code below).

Now I don't profess to be a master number cruncher, but the routines have served me well. I have actually developed these routines further (and given variables more specific names (huff_), removed those horrid "Exit" instructions etc), but as they form part of my "external data protection" I'm reluctant to release them at the moment.


Code :
Code: BlitzBasic
  1. ; Title:                Curve Compression (COMPRESS)
  2. ; Author:               Leigh Bowers
  3. ;                       (c) Copyright 2001 Curve Software
  4. ; Version:      1.0
  5. ;
  6. ; Email:                leigh.bowers@curvesoftware.co.uk
  7. ; WWW:          www.curvesoftware.co.uk/blitz
  8.  
  9. Type TreeNode
  10.     Field Weight%
  11.     Field SavedWeight%
  12.     Field Child1%
  13.     Field Child0%
  14. End Type
  15.  
  16. Type CharCodes
  17.     Field Code%
  18.     Field CodeBits%
  19. End Type
  20.  
  21. Type BitFile
  22.     Field Mask%
  23.     Field Rack%
  24.     Field OutputByteCount%
  25. End Type
  26.  
  27. Const SRCCOPY% = $CC0020
  28. Const ENDOFSTREAM% = 256
  29. Const ENDWEIGHTSTREAM% = $FFF
  30.  
  31. Dim Counters%(256)
  32. Dim Nodes.TreeNode(514)
  33. Dim Codes.CharCodes(257)
  34.  
  35. Global Bitio.BitFile
  36.  
  37. ; --------------
  38. ; Example Usage
  39. ; --------------
  40.  
  41. s$ = "source.bmp"
  42. Print "Curve Compression - Compress"
  43. Print ""
  44. Print "Source length:" + FileSize(s)
  45. Start# = MilliSecs()
  46. ;
  47. CompressFile s, "packed.dat" ; The extention can be anything (.dat, .pak, .abc etc)
  48. ;
  49. Finish# = MilliSecs()
  50. Print "Packed length:" + FileSize("packed.dat")
  51. Print ((Finish - Start)/1000) + " seconds taken."
  52. WaitKey
  53.  
  54. End
  55.  
  56. ; --------------
  57.  
  58. Function InitHuffman()
  59.  
  60.         Local i%
  61.  
  62.         For i = 0 To 514 : Nodes.TreeNode(i) = New TreeNode : Next
  63.         For i = 0 To 257 : Codes.CharCodes(i) = New CharCodes : Next
  64.         bitio.bitfile = New bitfile
  65.         BitioMask = $80
  66.  
  67. End Function
  68.  
  69. Function CountOccurrences(lSourceBank%, lSourceSize%)
  70.  
  71.         Local bChar%, l%
  72.  
  73.         For l = 0 To (lSourceSize - 1)
  74.                 bChar = PeekByte(lSourceBank, l)
  75.                 Counters(bChar) = Counters(bChar) + 1
  76.         Next
  77.  
  78. End Function
  79.  
  80. Function ScaleCounts()
  81.  
  82.         Local MaxCount%, i%
  83.    
  84.         MaxCount = 0
  85.         For i = 0 To 256
  86.                 If Counters(i) > MaxCount Then MaxCount = Counters(i)
  87.         Next
  88.        
  89.         MaxCount = (MaxCount / 255) + 1
  90.         For i = 0 To 256
  91.                 Nodes(i)Weight = Counters(i) / MaxCount
  92.                 If Nodes(i)Weight = 0 And Counters(i) <> 0 Then Nodes(i)Weight = 1
  93.         Next
  94.         Nodes(ENDOFSTREAM)Weight = 1
  95.  
  96. End Function
  97.  
  98. Function BuildTree%()
  99.  
  100.         Local NextFree%, i%, Min1%, Min2%
  101.    
  102.         Nodes(513)Weight = $7FFF
  103.         For NextFree = (EndOfStream + 1) To 514
  104.                 Min1 = 513
  105.                 Min2 = 513
  106.                 For i = 0 To (NextFree - 1)
  107.                         If Nodes(i)Weight <> 0 Then
  108.                                 If Nodes(i)Weight < Nodes(Min1)Weight Then
  109.                                         Min2 = Min1
  110.                                         Min1 = i
  111.                                 Else
  112.                                         If Nodes(i)Weight < Nodes(Min2)Weight Then Min2 = i
  113.                                 End If
  114.                         End If
  115.                 Next
  116.        
  117.                 If Min2 = 513 Then Exit
  118.  
  119.                 Nodes(NextFree)Weight = Nodes(Min1)Weight + Nodes(Min2)Weight
  120.                 Nodes(Min1)SavedWeight = Nodes(Min1)Weight
  121.                 Nodes(Min1)Weight = 0
  122.                 Nodes(Min2)SavedWeight = Nodes(Min2)Weight
  123.                 Nodes(Min2)Weight = 0
  124.                 Nodes(NextFree)Child0 = Min1
  125.                 Nodes(NextFree)Child1 = Min2
  126.         Next
  127.        
  128.         NextFree = NextFree - 1
  129.         Nodes(NextFree)SavedWeight = Nodes(NextFree)Weight
  130.  
  131.         Return NextFree
  132.  
  133. End Function
  134.  
  135. Function ConvertTreeToCode(CodeSoFar%, Bits%, node%)
  136.  
  137.         If node <= ENDOFSTREAM Then
  138.                 Codes(node)Code = CodeSoFar
  139.                 Codes(node)CodeBits = Bits
  140.                 Return
  141.         End If
  142.         CodeSoFar = CodeSoFar * 2
  143.         Bits = Bits + 1
  144.         ConvertTreeToCode CodeSoFar, Bits, Nodes(node)Child0
  145.         ConvertTreeToCode (CodeSoFar Or 1), Bits, Nodes(node)Child1
  146.         CodeSoFar = CodeSoFar / 2
  147.         Bits = Bits - 1
  148.  
  149. End Function
  150.  
  151. Function OutputCounts%(lDestBank%, lDestSize%)
  152.  
  153.         Local i%, FirstNode%, LastNode%, NextNode%
  154.        
  155.         FirstNode = 0
  156.         While (FirstNode < 256)
  157.                 If Nodes(FirstNode)SavedWeight <> 0 Then
  158.                         For LastNode = FirstNode + 1 To 255
  159.                             If Nodes(LastNode)SavedWeight = 0 Then Exit
  160.                         Next
  161.                         LastNode = LastNode - 1
  162.                         For NextNode = LastNode + 1 To 255
  163.                                 If Nodes(NextNode)SavedWeight = 0 Then
  164.                                         If (NextNode > 255) Or (NextNode - LastNode > 3) Then Exit
  165.                                 Else
  166.                                         LastNode = NextNode
  167.                                 End If
  168.                         Next
  169.                         PokeShort lDestBank, lDestSize, FirstNode : lDestSize = lDestSize + 2
  170.                         PokeShort lDestBank, lDestSize, LastNode : lDestSize = lDestSize + 2
  171.                         For i = FirstNode To LastNode
  172.                                 PokeShort lDestBank, lDestSize, Nodes(i)SavedWeight : lDestSize = lDestSize + 2
  173.                         Next
  174.                         FirstNode = NextNode + 1
  175.                 Else
  176.                         FirstNode = FirstNode + 1
  177.                 End If
  178.         Wend
  179.         PokeShort lDestBank, lDestSize, ENDWEIGHTSTREAM : lDestSize = lDestSize + 2
  180.        
  181.         Return lDestSize
  182.  
  183. End Function
  184.  
  185. Function CompressFile(sSource$, sDest$)
  186.  
  187.         Local iSymbol%, iBitcount%, bChar%
  188.         Local lSourceBank%, lDestBank%, lSourceSize%, lDestSize%
  189.        
  190.         InitHuffman
  191.  
  192.         ; Create Banks
  193.  
  194.         lSourceSize = FileSize(sSource)
  195.  
  196.         lSourceBank = CreateBank(lSourceSize)
  197.         lDestBank = CreateBank((lSourceSize + (lSourceSize * 0.01)) + 1000 ) ; Allow for 1% file increase
  198.  
  199.         ; Read source file in to bank
  200.  
  201.         hFileIn% = ReadFile(sSource)
  202.         ReadBytes lSourceBank, hFileIn, 0, lSourceSize
  203.         CloseFile hFileIn
  204.        
  205.         ; Pre-Processing
  206.        
  207.         CountOccurrences lSourceBank, lSourceSize
  208.         ScaleCounts()
  209.  
  210.         iRootNode% = BuildTree()
  211.         ConvertTreeToCode 0, 0, iRootNode
  212.        
  213.         ; Main Compression
  214.        
  215.         PokeInt lDestBank, 0, lSourceSize ; Store the original (uncompressed) file size at the head of the file
  216.  
  217.         lDestSize = OutputCounts(lDestBank, 4)
  218.  
  219.         For l% = 0 To (lSourceSize - 1)
  220.                 bChar = PeekByte(lSourceBank, l)
  221.                 iSymbol = Codes(bChar)Code
  222.                 iBitcount = Codes(bChar)CodeBits
  223.                 lDestSize = BitHandler(lDestBank, iSymbol, iBitcount, lDestSize)
  224.         Next
  225.  
  226.         iSymbol = Codes(ENDOFSTREAM)Code
  227.         iBitcount = Codes(ENDOFSTREAM)CodeBits
  228.         lDestSize = BitHandler(lDestBank, iSymbol, iBitcount, lDestSize)
  229.         If BitioMask <> $80 Then PokeByte lDestBank, lDestSize, BitioRack : lDestSize = lDestSize + 1
  230.  
  231.         FreeBank lSourceBank
  232.  
  233.         ; Write the compressed file
  234.  
  235.         hFileOut% = WriteFile(sDest)
  236.         WriteBytes lDestBank, hFileOut, 0, lDestSize
  237.         CloseFile hFileOut
  238.  
  239.         FreeBank lDestBank
  240.  
  241. End Function
  242.  
  243. Function BitHandler%(lDestBank%, iSymbol%, iBitcount%, lDestSize%)
  244.  
  245.         Local SymbolMask%, i%
  246.  
  247.         SymbolMask = 1
  248.         For i = 1 To (iBitcount - 1) : SymbolMask = SymbolMask * 2 : Next
  249.         While (SymbolMask <> 0)
  250.                 If (iSymbol And SymbolMask) Then BitioRack = BitioRack Or BitioMask
  251.                 SymbolMask = SymbolMask / 2
  252.                 BitioMask = BitioMask / 2
  253.                 If BitioMask = 0 Then
  254.                         PokeByte lDestBank, lDestSize, BitioRack : lDestSize = lDestSize + 1
  255.                         BitioMask = $80
  256.                         BitioRack = 0
  257.                         BitioOutputByteCount = BitioOutputByteCount + 2
  258.                 End If
  259.         Wend
  260.        
  261.         Return lDestSize
  262.  
  263. End Function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal