2009年11月20日金曜日

The Go Programming Language

Googleで開発中の新しい言語だ〜
The Go Programming Language
ちょっと面白そうかも。

Mac版 Google Chromeアップデートされた

バージョンが4.0.249.0になった。

2009年11月19日木曜日

RubyでGIFを読んでみた

gif.rb
class GIF
attr_accessor :version, :width, :height, :bgcolor_index, :aspect_ratio, :sort_flag
attr_accessor :color_table, :blocks

def self.load(istream)
self.new.load(istream)
end

def self.load_file(filename)
self.new.load_file(filename)
end

def initialize
@blocks = []
end

def [](index)
@blocks[index]
end

def []=(index, block)
@blocks[index] = block
end

def <<(block)
@blocks << block
end

def clear
@blocks = []
@version = @width = @height = @bgcolor_index = @aspect_ratio = @sort_flag =
@color_table = nil
end

def load(istream)
clear
reader = Reader.new(self, istream)
reader.run
end

def load_file(filename)
File.open(filename, 'rb'){|f| load(f) }
end

class GraphicControlExtension
attr_accessor :disposal_method, :user_input_flag, :delay_time, :transparent_index
# case disposal_method
# when 0; # no action is required
# when 1; # do not dispose
# when 2; # restore to background color
# when 3; # restore to previous
# end
end

class CommentExtension
attr_accessor :data
end

class PlainTextExtension
attr_accessor :x, :y, :width, :height, :cell_width, :cell_height
attr_accessor :fgcolor_index, :bgcolor_index
attr_accessor :text
end

class ApplicationExtension
attr_accessor :app_id, :auth_code, :data
end

class ImageBlock
attr_accessor :x, :y, :width, :height, :interlace_flag, :sort_flag, :color_table
attr_accessor :code_size, :data

def decode
LZW.decode(@code_size, @data)
end

def encode(indexes)
largest = indexes.sort[-1]
@code_size = ("%b" % largest).size
@code_size = 2 if 2 > @code_size
@data = LZW.encode(@code_size, indexes)
end

def encode_with_code_size(indexes, code_size)
@data = LZW.encode(@code_size = code_size, indexes)
end
end
end

######################################################################
class GIF::Reader
def initialize(gif, istream)
@gif = gif
@istream = istream
end

def run
read_header
read_blocks
@gif
end

def read_header
sig,
@gif.version, @gif.width, @gif.height,
bits,
@gif.bgcolor_index, @gif.aspect_ratio = read_fmt('a3a3vvCCC')

gctf = 0 != (0b1000_0000 & bits) # global color table flag
cr = (0b0111 & (bits >> 4)) + 1 # color resolution
@gif.sort_flag = 0 != (0b1000 & bits)
gct_size = 2 ** ((0b0111 & bits) + 1) # size of global color table
@gif.color_table = (0...gct_size).map{ read_fmt('CCC') } if gctf
end

def read_blocks
loop do
case block_type = read_fmt('C')[0]
when 0x3B # trailer
break
when 0x21 # Extension
@gif << read_extension_block
when 0x2C # Image
@gif << read_image_block
else
raise "Not Yet Impl : BlockType is 0x#{"%02x" % block_type}"
end
end
end

def read_extension_block
label = read_fmt('C')[0]
case label
when 0xF9 # Graphic Control
read_graphic_control
when 0xFE # Comment Label
read_comment_label
when 0x01 # Plain Text
read_plain_text
when 0xFF # Application Extension
read_application_extension
else
raise 'Not Yet Impl'
end
end

def read_graphic_control
b = GIF::GraphicControlExtension.new
block_size, bits, b.delay_time, b.transparent_index, zero = read_fmt('CCvCC')
b.disposal_method = 0b111 & (bits >> 2)
b.user_input_flag = 0 != 0b10 & bits
transparent_color_flag = 0 != 0b1 & bits
b.transparent_index = nil unless transparent_color_flag
b
end

def read_comment_label
b = GIF::CommentExtension.new
b.data = read_block_data
b
end

def read_plain_text
b = GIF::PlainTextExtension.new
block_size, b.x, b.y, b.width, b.height,
b.cell_width, b.cell_height,
b.fgcolor_index, b.bgcolor_index = read_fmt('CvvvvCCCC')
b.text = read_block_data
b
end

def read_application_extension
b = GIF::ApplicationExtension.new
block_size, b.app_id, b.auth_code = read_fmt('Ca8a3')
b.data = read_block_data
b
end

def read_block_data
bytes = ''
loop do
size = read_fmt('C')[0]
return bytes if size == 0
bytes << read(size)
end
end

def read_image_block
b = GIF::ImageBlock.new
b.x, b.y, b.width, b.height, bits = read_fmt('vvvvC')
lctf = (0 != 0x80 & bits) # local color table flag
b.interlace_flag = (0 != 0x40 & bits)
b.sort_flag = (0 != 0x20 & bits)
lct_size = 2 ** ((0x07 & bits) + 1)
b.color_table = (0...lct_size).map{ read_fmt('CCC') } if lctf
b.code_size = read_fmt('C')[0]
b.data = read_block_data
b
end

def read(size)
bytes = @istream.read(size)
raise 'End of file' if bytes.nil?
raise 'Not enough' if bytes.size != size
bytes
end

def read_fmt(fmt)
read(pack_size(fmt)).unpack(fmt)
end

def pack_size(fmt)
total_size = 0
item_size = 0
fmt.scan(/[a-zA-Z]|[0-9]+/).each do |v|
case v
when 'C'; item_size = 1
when 'a'; item_size = 1
when 'v'; item_size = 2
when /[0-9]+/
item_size *= v.to_i - 1
else
raise 'Not Yet'
end
total_size += item_size
end
total_size
end
end

######################################################################
module GIF::LZW
MAX_NBITS = 12

module_function
def encode(nbits, istring)
GIF::LZW::Encoder.encode(nbits, ArrayReader.new(istring), StringIO.new).string
end

def decode(nbits, istring)
GIF::LZW::Decoder.decode(nbits, StringIO.new(istring), StringIO.new).string
end

def bit_mask(nbits)
(1 << nbits) - 1
end
end

######################################################################
class GIF::LZW::Dictionary
attr_reader :clear_code, :end_code
def initialize(nbits)
dict_size = 1 << nbits
@dict = (0...dict_size).map{|k| [nil, k] }
@clear_code = dict_size
@dict << nil # Clear Code
@end_code = dict_size + 1
@dict << nil # End Code
@code = {}
end

def reset
@dict.slice!(@end_code + 1, @dict.size)
@code = {}
end

def size
@dict.size
end

def add(w, k)
new_code = @code[(w << 8) + k] = @dict.size
@dict << [w, k]
return new_code
end

def code(w, k)
return k unless w
return @code[(w << 8) + k]
end

def string(code)
w, k = @dict[code]
return nil unless k
return string(w) << k if w
return [k]
end
end

######################################################################
# src[0] : <abcde> : 11100
# src[1] : <fghij> : 11000
# src[2] : <klmno> : 10000
#
# dst[0] : <hijabcde> : 00011100
# dst[1] : <.klmnofg> : 01000011
class GIF::LZW::BitWriter
attr_reader :stream

def initialize(stream)
@stream = stream
@value = @nbits = 0
end

def write(value, nbits)
@value |= (GIF::LZW.bit_mask(nbits) & value) << @nbits
@nbits += nbits
while 8 <= @nbits
@stream.write([0xFF & @value].pack('C'))
@value >>= 8
@nbits -= 8
end
end

def flush
if 0 < @nbits
@stream.write([0xFF & @value].pack('C'))
@value = @nbits = 0
end
@stream.flush
end
end

######################################################################
class GIF::LZW::BitReader
attr_reader :stream

def initialize(stream)
@stream = stream
@value = @nbits = 0
end

def read(nbits)
while @nbits < nbits
byte = @stream.read(1)
return nil unless byte
byte = byte.unpack('C')[0]
@value |= byte << @nbits
@nbits += 8
end
v = GIF::LZW.bit_mask(nbits) & @value
@value >>= nbits
@nbits -= nbits
return v
end
end

######################################################################
class GIF::LZW::ArrayReader
def initialize(array)
@array = array
@pos = 0
end

def getc
if @pos < @array.size
pos = @pos
@pos += 1
return @array[pos]
end
end
end

######################################################################
class GIF::LZW::Encoder
# @return ostream
def self.encode(nbits, istream, ostream)
encoder = self.new(nbits, istream, ostream)
encoder.run
end

def initialize(nbits, istream, ostream)
@nbits = nbits
@istream = istream
@bit_writer = GIF::LZW::BitWriter.new(ostream)
@code_size = nbits + 1
@dict = GIF::LZW::Dictionary.new(@nbits)
@w = nil
write_code(@dict.clear_code)
end

def run
while k = @istream.getc
write(k)
end
finish
end

def write(k)
if c = @dict.code(@w, k)
@w = c
return
end

c = @dict.add(@w, k)
write_code(@w)
@w = k

return if (1 << @code_size) != c

if @code_size < GIF::LZW::MAX_NBITS
@code_size += 1
return
end

write_code(@dict.clear_code)
@code_size = @nbits + 1
@dict.reset
end

def finish
write_code(@w) if @w
write_code(@dict.end_code)
@bit_writer.flush
end

def write_code(code)
@bit_writer.write(code, @code_size)
end
end

######################################################################
class GIF::LZW::Decoder
# @return ostream
def self.decode(nbits, istream, ostream)
decoder = self.new(nbits, istream, ostream)
decoder.run
end

def initialize(nbits, istream, ostream)
@nbits = nbits
@bit_reader = GIF::LZW::BitReader.new(istream)
@ostream = ostream
@code_size = nbits + 1
@dict = GIF::LZW::Dictionary.new(@nbits)
end

def run
decode_1st && while decode_2nd; end
@ostream.flush
end

def decode_1st
@w = read_code
@w = read_code while @dict.clear_code == @w
return nil if @w.nil? || @dict.end_code == @w
@ws = @dict.string(@w)
@ostream.write(@ws.pack('C*'))
true
end

def decode_2nd
@code_size += 1 if @dict.size == (1 << @code_size) && @code_size < GIF::LZW::MAX_NBITS
k = read_code

return if k.nil? || @dict.end_code == k

if @dict.clear_code == k
@code_size = @nbits + 1
@dict.reset
return decode_1st
end

ks = @dict.string(k)
ks = @ws + @ws.slice(0, 1) unless ks
@ostream.write(ks.pack('C*'))
@dict.add(@w, ks[0])
@w, @ws = k, ks
end

def read_code
@bit_reader.read(@code_size)
end
end

LZWをRubyで実装してみた

lzw.rb
#
# LZW Algorithm
#
class Dic
def initialize
@dict = (0...256).map{|k| [nil, k]}
@code = {}
end

def add(w, k)
new_code = @code[(w << 8) + k] = @dict.size
@dict << [w, k]
return new_code
end

def code(w, k)
return k unless w
return @code[(w << 8) + k]
end

def string(code)
w, k = @dict[code]
return nil unless k
return string(w) << k if w
return [k]
end
end

def encode(input)
output = []
dic = Dic.new
w = nil
while k = input.shift
c = dic.code(w, k)
if c
w = c
else
output << w
dic.add(w, k)
w = k
end
end
output << w if w
return output
end

def decode(input)
output = []
dic = Dic.new
w = input.shift
return output unless w
ws = dic.string(w)
ws.each{|v| output << v}
while k = input.shift
ks = dic.string(k)
ks = ws + ws.slice(0, 1) unless ks
ks.each{|v| output << v}
dic.add(w, ks[0])
w, ws = k, ks
end
return output
end

encode([0,1,0,1,0,1,0,1]) # => [0, 1, 256, 258, 1]
decode([0,1,256,258,1]) # => [0, 1, 0, 1, 0, 1, 0, 1]