This is a little bit late (Wednesday), and doesn't behave as I
originally thought it ought to behave, because I don't have time to do
the different-operations-choose-types-differently properly. (the basic
idea is to coerce Integers to a class that wraps an Integer and does
coercions in different ways when presented with different operations)
Like most others, I implemented each differently sized FWI as a
separate class. In my code, one creates a new value by doing:
u_int_eight = FWI.new(32,false).new(8)
However, I also implement two other syntaxes (the syntax of the
original quiz spec and the syntax of Sander Land's test case) for
convenience. However, the number of bits aren't confined to any fixed
set; instead, classes are created on the fly as needed. (After using
the class a bit in irb, ask for FWI.constants)
As I worked on this quiz, I got into the idea of implementing C
arithmetic as closely as possible. This is significantly trickier
than it might appear at first; consider this C program:
int main(int argc, char *argv)
{
unsigned short int u_four = 4;
short int four = 4;
long int l_neg_nine = -9;
printf("The division yields %ld\n", l_neg_nine / u_four);
printf("The modulus yields %ld\n", l_neg_nine % u_four);
printf("The all signed division yields %ld\n", l_neg_nine / four);
printf("The all signed modulus yields %ld\n", l_neg_nine % four);
}
What should it produce? Well, it turns out that even if you know the
size of "long" and "short" ints (32 and 16 bits on most modern
machines), the result depends on whether you're using a compiler that
follows ansi C numeric rules or the rules of K&R C. (The second two
lines are the same under both sets of rules, but the first two lines
aren't)
Even then, there's also the issue that C and Ruby disagree on how
integer division and remainder should behave with negative numbers.
As everyone who's dealt with C much should know, -9/4 (assuming
everything is signed and long enough) is -2. However, in Ruby:
irb(main):001:0> -9 / 4
=> -3
That is, C produces (a*1.0/b).truncate whereas Ruby produces
(a*1.0/b).floor - I'll note that Python agrees with Ruby in this.
Perl simply promotes integers to floats when the division isn't
exact.
The definition of % in both C and Ruby is consistent with the
definition of integer /; this means that in C, -9 % 4 is -1 but in
Ruby -9 % 4 is 3. Note that I think that the Ruby behavior makes much
more sense, mathematically, and both Python and Perl agree with this
behavior. Still, it makes emulating C arithmetic (say, if one were
copying an algorithm from ancient source code) tricky.
My solution was to add two new methods to Integer: c_div and
c_modulo. These implementinteger division and integer mod with C
semantics. I also then added a class method called c_math that takes
three arguments (two operands and an operation) and does the
equivalent of statements like this:
int c = a / b;
Including promoting a and b to a common type and doing the
cast-to-signed-int if necessary. This method uses c_div and c_modulo
when appropriate.
Thinking of other uses of this FWI class, specifically of how it could
be useful in translating algorithms, led me to add a few x86 assembly
language operations. After all, fixed width integers are all over the
place in assembly, and it's perfectly conceivable that someone might
want to translate an algorithm from ancient 8086 assembly into ruby
for a modern machine. In this version, I've only added one assembly
operation (rcl - rotate left through carry) since the demonstrations
of the other operations weren't very interesting after all.
So here's the code. First, the file fwi_use.rb that demonstrates some
uses of the class: it reimplements the C program above in both K&R
mode and ansi mode, and then implements the CRC algorithm used in
xmodem (adapted from assembly code).
======================= fwi_use.rb ===========================
# The following C program was typed into t.c and then
# compiled with gcc in K&R mode, and gcc in ansi mode.
# The results are below.
···
#
# int main(int argc, char *argv)
# {
# unsigned short int u_four = 4;
# short int four = 4;
# long int l_neg_nine = -9;
#
# printf("The division yields %ld\n", l_neg_nine / u_four);
# printf("The modulus yields %ld\n", l_neg_nine % u_four);
#
# printf("The all signed division yields %ld\n", l_neg_nine / four);
# printf("The all signed modulus yields %ld\n", l_neg_nine % four);
# }
#
# esau:~$ gcc-2.95 -traditional -o t t.c && ./t
# The division yields 1073741821
# The modulus yields 3
# The all signed division yields -2
# The all signed modulus yields -1
# esau:~$ gcc-2.95 -ansi -o t t.c && ./t
# The division yields -2
# The modulus yields -1
# The all signed division yields -2
# The all signed modulus yields -1
require 'fwi'
u_four = FWI.new(16,false).new(4)
four = FWI.new(16,true).new(4)
l_neg_nine = FWI.new(32,true).new(-9)
FWI.new(32).set_coerce_method(:kr)
puts "K&R Math:"
print("The division yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :/, u_four)])
print("The modulus yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :%, u_four)])
print("The all signed division yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :/, four)])
print("The all signed modulus yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :%, four)])
FWI.new(32).set_coerce_method(:ansi)
puts "\nansi Math:"
print("The division yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :/, u_four)])
print("The modulus yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :%, u_four)])
print("The all signed division yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :/, four)])
print("The all signed modulus yields %d\n" %
[FWI.new(32).c_math(l_neg_nine, :%, four)])
FWI.new(32).set_coerce_method(:first)
puts "\nRuby Math:"
print("The division yields %d\n" %
[l_neg_nine / u_four])
print("The modulus yields %d\n" %
[l_neg_nine % u_four])
print("The all signed division yields %d\n" %
[l_neg_nine / four])
print("The all signed modulus yields %d\n" %
[l_neg_nine % four])
# CRC test
# adapted from the assembly-language routines at
# http://www.wps.com/FidoNet/source/DOS-C-sources/Old%20DOS%20C%20library%20source/crc.asm
def xmodem_crc(a,prev_crc=FWI.new(16,false).new(0))
crc = prev_crc
a.each_byte{ |al_val|
al = FWI.new(8,false).new(al_val)
8.times {
al.rcl!(1)
crc.rcl!(1)
crc ^= 0x1021 if FWI::FWIBase.carry>
}
}
crc
end
def add_crc(s)
a = s + "\x00\x00"
crc = xmodem_crc(a)
a[-2] = crc.to_i >> 8
a[-1] = crc.to_i & 0xFF
a
end
def check_crc(s)
xmodem_crc(s) == 0
end
puts "\nAdding a crc to a classic string:"
a = add_crc('Hello World!')
p a
puts "Modifying:"
a[1] = ?i
p a
puts "check_crc yields: " + check_crc(a).inspect
a[1] = ?e
p a
puts "check_crc yields: " + check_crc(a).inspect
__END__
================ fwi.rb ======================
class Integer
def c_modulo(o)
if ((self >= 0 and o >= 0) or (self <=0 and o < 0))
return self % o
else
return 0 if (self % o) == 0
return (self % o) - o
end
end
def c_div(o)
return((self - self.c_modulo(o))/o);
end
end
class FWI
class FWIBase
attr_reader :rawval
include Comparable
@@carry = 0
def initialize(n)
@rawval = n.to_i & maskval
@@carry = (n.to_i != to_i) ? 1 : 0
end
def FWIBase.carry; @@carry; end
def FWIBase.carry?; @@carry==1; end
def maskval; 0xF; end
def nbits; 4; end
def signed?; false; end
def to_i; rawval; end
def to_s; to_i.to_s; end
#def inspect; "<0x%0#{(nbits/4.0).ceil}x;%d>" % [rawval,to_i]; end
def inspect; to_s; end
def hash; to_i.hash; end
def coerce(o)
return self.class.fwi_coerce(o,self) if o.is_a? Integer
to_i.coerce(o)
end
def ==(o)
if (o.is_a? FWIBase) then
to_i == o.to_i
else
to_i == o
end
end
def eql?(o)
o.class == self.class and self == o
end
def FWIBase.set_coerce_method(meth)
case meth
when :kr
class << self
def fwi_coerce(a,b)
c = FWI.kr_math_class(a,b)
[c.new(a),c.new(b)]
end
end
when :ansi
class << self
def fwi_coerce(a,b)
c = FWI.ansi_math_class(a,b)
[c.new(a),c.new(b)]
end
end
when :first
class << self
def fwi_coerce(a,b)
return [a,b.to_i] if a.is_a? Integer
[a,a.class.new(b)]
end
end
when :second
class << self
def fwi_coerce(a,b)
return [a.to_i,b] if b.is_a? Integer
[b.class.new(a),b]
end
end
else
class << self
self.send(:undef_method,:fwi_coerce)
end
end
end
%w(+ - / * ^ & | ** % << >> c_div c_modulo div modulo).each { |op|
ops = op.to_sym
FWIBase.send(:define_method,ops) { |o|
if (o.class == self.class)
self.class.new(to_i.send(ops,o.to_i))
elsif o.is_a? Integer or o.is_a? FWIBase then
b = self.class.fwi_coerce(self,o)
b[0].send(ops,b[1])
else
to_i.send(ops,o)
end
}
}
%w(-@ +@ ~).each { |op|
ops = op.to_sym
FWIBase.send(:define_method,ops) {
self.class.new(to_i.send(ops))
}
}
def <=>(o)
to_i.<=>(o)
end
# And now add a few x86 assembly operations
# I only bother with rcl here, but for completeness
# one could easily implement rcr, rol, ror, adc, sbb, etc.
def rcl(n=1)
lbits = n % (nbits+1)
big = @rawval << lbits
big |= (FWIBase.carry << (lbits-1))
self.class.new((big & (2*maskval+1)) | (big >> (nbits+1)))
end
def rcl!(n)
@rawval = maskval && rcl(n).to_i
end
def FWIBase.c_math(a, op, b)
op = :c_div if op == 
op = :c_modulo if op == :%
a,b = self.fwi_coerce(a,b)
self.new(a.send(op,b))
end
end
@@clazzhash = Hash.new {|h,k|
l1 = __LINE__
FWI.class_eval(%Q[
class FWI_#{k} < FWI::FWIBase
def initialize(n); super(n); end
def maskval; #{(1<<k) - 1};end
def signed?; false; end
def nbits; #{k}; end
end
class FWI_#{k}_S < FWI_#{k}
def signed?; true; end
def to_i
if rawval < #{1<<(k-1)} then
rawval
else
rawval - #{1<<k}
end
end
end
], __FILE__, l1+1)
h[k] = FWI.class_eval(%Q"[FWI_#{k},FWI_#{k}_S]",
__FILE__, __LINE__ - 1)
}
def FWI.new(n,signed=true)
@@clazzhash[n][signed ? 1 : 0]
end
# K&R-like
# First, promote both to the larger size.
# Promotions of smaller to larger preserve unsignedness
# Once promotions are done, result is unsigned if
# either input is unsigned
def FWI.kr_math_class(a,b)
return b.class if (a.is_a? Integer)
return a.class if (b.is_a? Integer)
nbits = a.nbits
nbits = b.nbits if b.nbits > nbits
signed = a.signed? && b.signed?
FWI.new(nbits,signed)
end
# ANSI C-like
# promotions of smaller to larger promote to signed
def FWI.ansi_math_class(a,b)
return b.class if (a.is_a? Integer)
return a.class if (b.is_a? Integer)
nbits = a.nbits
nbits = b.nbits if b.nbits > nbits
signed = true
signed &&= a.signed? if (a.nbits == nbits)
signed &&= b.signed? if (b.nbits == nbits)
FWI.new(nbits,signed)
end
FWIBase.set_coerce_method(:ansi)
end
# support the syntax from the quiz spec
class UnsignedFixedWidthInt
def UnsignedFixedWidthInt.new(width,val)
FWI.new(width,false).new(val)
end
end
class SignedFixedWidthInt
def SignedFixedWidthInt.new(width,val)
FWI.new(width,true).new(val)
end
end
# support the syntax in Sander Land's test case
def UnsignedFWI(width)
FWI.new(width,false)
end
def SignedFWI(width)
FWI.new(width,true)
end
__END__
