What's the best way to calculate if a byte has odd or even parity in Ruby? I've got a version working:
result = "AB".to_i(16).to_s(2).count('1').odd?
=> true
Converting a number to a string and counting the "1"s seems a poor way of calculating parity though. Any better methods?
I want to be able to calculate the parity of a 3DES key. Eventually, I'll want to convert even bytes to odd.
Thanks, Dan
Unless what you have is not fast enough, keep it. It's clear and succinct, and its performance is better than you think.
We'll benchmark everything against array lookup, the fastest method I tested:
ODD_PARITY = [
false,
true,
true,
...
true,
false,
]
def odd_parity?(hex_string)
ODD_PARITY[hex_string.to_i(16)]
end
Have you taken a look at the RubyDES library? That may remove the need to write your own implementation.
To calculate parity, you can use something like the following:
require 'rubygems'
require 'inline' # RubyInline (install with `gem install RubyInline`)
class Fixnum
# native ruby version: simpler but slow
# algorithm from:
# http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel
def parity_native
(((self * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1
end
class << self
# inline c version using RubyInline to create c extension
# 4-5 times faster than native version
# use as class method:
# Fixnum.parity(0xAB)
inline :C do |builder|
builder.c <<-EOC
int parity_c(int num) {
return (
((num * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF
) & 1;
}
EOC
end
end
def parity
self.class.parity_c(self)
end
def parity_odd?
1 == parity
end
def parity_even?
0 == parity
end
end
0xAB.parity # => 1
0xAB.parity_odd? # => true
0xAB.parity_even? # => false
(0xAB + 1).parity # => 0
According to simple benchmarks, the inline c version is 3-4 times faster than the native ruby version
require 'benchmark'
n = 10000
Benchmark.bm do |x|
x.report("inline c") do
n.times do
(0..255).map{|num| num.parity}
end
end
x.report("native ruby") do
n.times do
(0..255).map{|num| num.parity_native}
end
end
end
# inline c 1.982326s
# native ruby 7.044330s
Probably a lookup table of an Array with 255 entries would be fastest "In Ruby" solution.
In C I would mask and shift. Or if I have SSE4 I would use the POPCNT instruction with inline assembler. If you need this to be high performance write a native extension in C which does either of the above.
How about using your original solution with memoization? This will only calculate once for each integer value.
class Fixnum
# Using a class variable for simplicity, and because subclasses of
# Fixnum—while very uncommon—would likely want to share it.
@@parity = ::Hash.new{ |h,i| h[i] = i.to_s(2).count('1').odd? }
def odd_parity?
@@parity[self]
end
def even_parity?
!@@parity[self]
end
end
"AB".to_i(16).odd_parity?
#=> true
I would construct a single table of 16 entries (as a 16 character table), corresponding to each nibble (half) of a bytes. Entries are 0,1,1,2,1,2,....4
To test your byte,
Mask out the left nibble and do a lookup, memorizing the number. Do. a shift to the right by 4 and do a second lookup, adding the result number to the previous one to provide a sum.
Then test the low order bit from the sum. If it is 1, the byte is odd, if it is a 0, the byte is even. If result is even, you flip the high order bit, using the xor instruction. THis lookup method is much faster than adding up the bits in a byte by single shifts.
email me for a simple function to do the parity for 8 bytes. 3DES uses 3 groups of 8 bytes.
x = 'AB'.to_i(16)
p = 0
until x == 0
p += x & 1
x = x >> 1
end
puts p # => 5
which can be shortened to
x = 'AB'.to_i(16)
p = x & 1
p += x & 1 until (x >>= 1) == 0
if you want something that is unreadable ☺
