Created
December 2, 2015 14:25
-
-
Save mlehmk/f5c43949392dd639dd95 to your computer and use it in GitHub Desktop.
Compression
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.IO; | |
| using System.Linq; | |
| using System.Security.Permissions; | |
| using System.Text; | |
| namespace Compression | |
| { | |
| public class RangeCoder : IDisposable | |
| { | |
| private uint low; | |
| private uint high; | |
| private const uint mask = 0x80000000u; | |
| private uint code; | |
| private int bits; | |
| private int octet; | |
| private Stream stream; | |
| private bool owningStream; | |
| private bool writing; | |
| public RangeCoder(Stream stream, bool writing, bool leaveOpen) | |
| { | |
| low = 0; | |
| high = uint.MaxValue; | |
| bits = 0; | |
| octet = 0; | |
| code = 0; | |
| this.writing = writing; | |
| owningStream = !leaveOpen; | |
| if (!writing) | |
| { | |
| for (int i = 0; i < 32; ++i) | |
| { | |
| code <<= 1; | |
| code |= GetBit(); | |
| } | |
| } | |
| } | |
| public event Action<byte> EmitOctet; | |
| protected void EmitBit(uint bit) | |
| { | |
| octet <<= 1; | |
| octet |= bit == 0 ? 0 : 1; | |
| if (++bits == 8) | |
| { | |
| stream?.WriteByte((byte) octet); | |
| EmitOctet?.Invoke((byte) octet); | |
| octet = 0; | |
| bits = 0; | |
| } | |
| } | |
| public void Flush() | |
| { | |
| while (bits > 0) | |
| { | |
| Encode(1, 2, 4); | |
| } | |
| } | |
| public void Encode(int index, int[] counts) | |
| { | |
| int start = counts.Take(index).Sum(); | |
| int size = counts[index]; | |
| int total = start + counts.Skip(index).Sum(); | |
| Encode(start, size, total); | |
| } | |
| public void Encode(int start, int size, int total) | |
| { | |
| long range = unchecked(high - low + 1) / total; // range overflows to 0 on full range | |
| if (range == 0) range = uint.MaxValue / total; | |
| checked | |
| { | |
| low += (uint) (start*range); | |
| high = (uint) (low + size*range - 1); | |
| } | |
| if (((low ^ high) & mask) == 0) | |
| { | |
| if (writing) | |
| { | |
| EmitBit(low & mask); | |
| low <<= 1; | |
| high <<= 1; | |
| high |= 1; | |
| } | |
| else | |
| { | |
| code <<= 1; | |
| code |= GetBit(); | |
| } | |
| } | |
| } | |
| private uint GetBit() | |
| { | |
| if (bits < 0) return 0; | |
| if (bits == 0) | |
| { | |
| octet = stream.ReadByte(); | |
| if (octet < 0) | |
| { | |
| octet = 0; | |
| bits = -1; | |
| } | |
| } | |
| --bits; | |
| octet <<= 1; | |
| return (octet & 0x100) == 0 ? 0u : 1u; | |
| } | |
| public int Decode(int[] counts) | |
| { | |
| int total = counts.Sum(); | |
| int start = 0; | |
| int value = Decode(total); | |
| int i; | |
| int size = total; | |
| for (i = 0; i < counts.Length; ++i) | |
| { | |
| size = counts[i]; | |
| if (start + size > value) break; | |
| start += size; | |
| } | |
| Encode(start, size, total); | |
| return i; | |
| } | |
| public int Decode(int total) | |
| { | |
| long range = unchecked(high - low + 1) / total; // range overflows to 0 on full range | |
| if (range == 0) range = uint.MaxValue / total; | |
| return (int) ((code - low)/(range/total)); | |
| } | |
| public void Dispose() | |
| { | |
| Flush(); | |
| if (owningStream && stream != null) | |
| { | |
| stream.Dispose(); | |
| stream = null; | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment