huff03.m

图像压缩的Huffman编码与解码,matlab源代码

% since it is always include in the two first bytes
% HuffTabLen returns how many bit needed to store Huffman-table/tree 
% Method is from 1 to 4, if Method is 0, all metheods are
% done and HLlen is returned as a vector
%  Method 1: (max codeword length is 15)
%         2 bit for method, '00'
%         6-18 bit is VLIC for number of symbols
%         4 bit to give length of first symbol
%        Then for each of the next symbols a code to tell its length
%         '0'             - same length as previous symbol
%         '10'            - increase length by 1
%         '1100'          - reduce length by 1
%         '1101'          - increase length by 2
%         '111xxxx'       - set symbol length to xxxx
%  Method 2: (max codeword length is 15)
%         2 bit for method, '01'
%         6-18 bit is VLIC for number of symbols
%         4 bit to give length of each symbol
%  Method 3: (max codeword length is 15)
%         2 bit for method, '10'
%         6-18 bit is VLIC for number of symbols
%         4 bit to give length of first symbol
%        Then for next symbols
%         '00'+VLIC       - VLIC symbols with same length as previous symbol
%         '01'            - increase length by 1
%         '10'            - reduce length by 1
%         '110'           - increase length by 2
%         '111xxxx'       - set symbol length to xxxx
%  Method 4: (max codeword length is 31)
%         2 bit for method, '11'
%         6-18 bit is VLIC for number of symbols
%         5 bit to give length of first symbol
%        Then for next symbols
%         '0'+VLIC        - VLIC symbols with same length as previous symbol
%         '10'            - increase length by 1
%         '11xxxxx'       - set symbol length to xxxxx
%
function HLlen = HuffTabLen(HL,Method)
L=length(HL);
StartBits=8;
if (L>=16); StartBits=StartBits+4; end;
if (L>=272); StartBits=StartBits+4; end;
if (L>=4368); StartBits=StartBits+4; end;
if (max(HL) >= 16); Method=4; end;
if (Method==0); HLlen=[1,1,1,1]*999999; else; HLlen=999999; end;
HLi=0;
if ((Method==0) | (Method==1))
   b=StartBits+4;    % include first length
   for l=2:L
      if (HL(l)==HL(l-1)); b=b+1;
      elseif (HL(l)==(HL(l-1)+1)); b=b+2;
      elseif (HL(l)==(HL(l-1)-1)); b=b+4;
      elseif (HL(l)==(HL(l-1)+2)); b=b+4;
      else; b=b+7;
      end
   end
   HLi=HLi+1;
   HLlen(HLi)=b;   
end
if ((Method==0) | (Method==2))
   HLi=HLi+1;
   HLlen(HLi)=StartBits+4*L;   
end
if ((Method==0) | (Method==3))
   b=StartBits+4;    % include first length
   r=0;
   for l=2:L
      if (HL(l)==HL(l-1)); r=r+1;
      else
         if r>0
            b=b+8;
            if (r>=16); b=b+4; end;
            if (r>=272); b=b+4; end;
            if (r>=4368); b=b+4; end;
            r=0;
         end
         if (HL(l)==(HL(l-1)+1)); b=b+2; 
         elseif (HL(l)==(HL(l-1)-1)); b=b+2;
         elseif (HL(l)==(HL(l-1)+2)); b=b+3;
         else b=b+7;
         end
      end
   end
   if r>0
      b=b+8;
      if (r>=16); b=b+4; end;
      if (r>=272); b=b+4; end;
      if (r>=4368); b=b+4; end;
      r=0;
   end
   HLi=HLi+1;
   HLlen(HLi)=b;   
end
if ((Method==0) | (Method==4))
   b=StartBits+5;    % include first length
   r=0;
   for l=2:L
      if (HL(l)==HL(l-1)); r=r+1;
      else
         if r>0
            b=b+7;
            if (r>=16); b=b+4; end;
            if (r>=272); b=b+4; end;
            if (r>=4368); b=b+4; end;
            r=0;
         end
         if (HL(l)==(HL(l-1)+1)); b=b+2; 
         else b=b+7;
         end
      end
   end
   if r>0
      b=b+7;
      if (r>=16); b=b+4; end;
      if (r>=272); b=b+4; end;
      if (r>=4368); b=b+4; end;
      r=0;
   end
   HLi=HLi+1;
   HLlen(HLi)=b;   
end
return;  % end of HuffTabLen

function PutHuffTab(HL,Method)
global y Byte BitPos
L=length(HL);
if (max(HL) >= 16); Method=4; end;
if (Method==1)
   PutBit(0);PutBit(0);PutVLIC(L);
   for (i=4:-1:1); PutBit(bitget(HL(1),i)); end;
   for l=2:L
      if (HL(l)==HL(l-1)); PutBit(0);
      elseif (HL(l)==(HL(l-1)+1)); PutBit(1);PutBit(0);
      elseif (HL(l)==(HL(l-1)-1)); PutBit(1);PutBit(1);PutBit(0);PutBit(0);
      elseif (HL(l)==(HL(l-1)+2)); PutBit(1);PutBit(1);PutBit(0);PutBit(1);
      else 
         PutBit(1);PutBit(1);PutBit(1);
         for (i=4:-1:1); PutBit(bitget(HL(l),i)); end;
      end
   end
end
if (Method==2)
   PutBit(0);PutBit(1);PutVLIC(L);
   for l=1:L
      for (i=4:-1:1); PutBit(bitget(HL(l),i)); end;
   end
end
if (Method==3)
   PutBit(1);PutBit(0);PutVLIC(L);
   for (i=4:-1:1); PutBit(bitget(HL(1),i)); end;
   r=0;
   for l=2:L
      if (HL(l)==HL(l-1)); r=r+1;
      else
         if r>0
            PutBit(0);PutBit(0);PutVLIC(r);r=0;
         end
         if (HL(l)==(HL(l-1)+1)); PutBit(0);PutBit(1); 
         elseif (HL(l)==(HL(l-1)-1)); PutBit(1);PutBit(0);
         elseif (HL(l)==(HL(l-1)+2)); PutBit(1);PutBit(1);PutBit(0);
         else 
            PutBit(1);PutBit(1);PutBit(1);
            for (i=4:-1:1); PutBit(bitget(HL(l),i)); end;
         end
      end
   end
   if r>0
      PutBit(0);PutBit(0);PutVLIC(r);r=0;
   end
end
if (Method==4)
   PutBit(1);PutBit(1);PutVLIC(L);
   for (i=5:-1:1); PutBit(bitget(HL(1),i)); end;
   r=0;
   for l=2:L
      if (HL(l)==HL(l-1)); r=r+1;
      else
         if r>0
            PutBit(0);PutVLIC(r);r=0;
         end
         if (HL(l)==(HL(l-1)+1)); PutBit(1);PutBit(0); 
         else 
            PutBit(1);PutBit(1);
            for (i=5:-1:1); PutBit(bitget(HL(l),i)); end;
         end
      end
   end
   if r>0
      PutBit(0);PutVLIC(r);r=0;
   end
end
return;  % end of PutHuffTab

function HL=GetHuffTab
global y Byte BitPos
if GetBit
   if GetBit; Method=4; else; Method=3; end;
else
   if GetBit; Method=2; else; Method=1; end;
end
L=GetVLIC;
HL=zeros(L,1);
if (Method==1)
   for (i=1:4); HL(1)=HL(1)*2+GetBit; end;
   for l=2:L
      if GetBit
         if GetBit
            if GetBit
               for (i=1:4); HL(l)=HL(l)*2+GetBit; end;
            else
               if GetBit
                  HL(l)=HL(l-1)+2;
               else
                  HL(l)=HL(l-1)-1;
               end
            end
         else
            HL(l)=HL(l-1)+1;
         end
      else
         HL(l)=HL(l-1);
      end
   end
end
if (Method==2)
   for l=1:L
      for (i=1:4); HL(l)=HL(l)*2+GetBit; end;
   end
end
if (Method==3)
   for (i=1:4); HL(1)=HL(1)*2+GetBit; end;
   l=1;
   while l<L
      l=l+1;
      if GetBit
         if GetBit
            if GetBit
               for (i=1:4); HL(l)=HL(l)*2+GetBit; end;
            else
               HL(l)=HL(l-1)+2;
            end
         else
            HL(l)=HL(l-1)-1;
         end
      else
         if GetBit
            HL(l)=HL(l-1)+1;
         else
            r=GetVLIC;
            HL(l:(l+r-1))=HL(l-1);
            l=l+r-1;
         end
      end
   end
end
if (Method==4)
   for (i=1:5); HL(1)=HL(1)*2+GetBit; end;
   l=1;
   while l<L
      l=l+1;
      if GetBit
         if GetBit
            for (i=1:5); HL(l)=HL(l)*2+GetBit; end;
         else
            HL(l)=HL(l-1)+1;
         end
      else
         r=GetVLIC;
         HL(l:(l+r-1))=HL(l-1);
         l=l+r-1;
      end
   end
end
return;  % end of GetHuffTab

% Functions to write and read a Variable Length Integer Code word
% This is a way of coding non-negative integers that uses fewer 
% bits for small integers than for large ones. The scheme is:
%   '00' +  4 bit  - integers from 0 to 15
%   '01' +  8 bit  - integers from 16 to 271
%   '10' + 12 bit  - integers from 272 to 4367
%   '11' + 16 bit  - integers from 4368 to 69903
%   not supported  - integers >= 69904
function PutVLIC(N)
global y Byte BitPos
if (N<0)
   error('huff03-PutVLIC: Number is negative.'); 
elseif (N<16)
   PutBit(0);PutBit(0);
   for (i=4:-1:1); PutBit(bitget(N,i)); end;
elseif (N<272)
   PutBit(0);PutBit(1);
   N=N-16;
   for (i=8:-1:1); PutBit(bitget(N,i)); end;
elseif (N<4368)
   PutBit(1);PutBit(0);
   N=N-272;
   for (i=12:-1:1); PutBit(bitget(N,i)); end;
elseif (N<69904)
   PutBit(1);PutBit(1);
   N=N-4368;
   for (i=16:-1:1); PutBit(bitget(N,i)); end;
else
   error('huff03-PutVLIC: Number is too large.'); 
end
return

function N=GetVLIC
global y Byte BitPos
N=0;
if GetBit
   if GetBit
      for (i=1:16); N=N*2+GetBit; end;
      N=N+4368;
   else
      for (i=1:12); N=N*2+GetBit; end;
      N=N+272;
   end
else
   if GetBit
      for (i=1:8); N=N*2+GetBit; end;
      N=N+16;
   else
      for (i=1:4); N=N*2+GetBit; end;
   end
end
return

% Functions to write and read a Bit
function PutBit(Bit)
global y Byte BitPos
BitPos=BitPos-1;
if (~BitPos); Byte=Byte+1; BitPos=8; end; 
y(Byte) = bitset(y(Byte),BitPos,Bit);
return
   
function Bit=GetBit
global y Byte BitPos
BitPos=BitPos-1;
if (~BitPos); Byte=Byte+1; BitPos=8; end; 
Bit=bitget(y(Byte),BitPos);
return;