Obliczanie parzystości bajta w Rubim

Question

Jaki jest najlepszy sposób obliczenia, czy bajt ma parzystość nieparzystą, czy parzystą w Ruby? Mam pracę wersji:

result = "AB".to_i(16).to_s(2).count('1').odd? 
=> true 

Konwersja liczby na łańcuch i liczenia „1” s wydaje się słabe sposób obliczania parytetu chociaż. Jakieś lepsze metody?

Chcę być w stanie obliczyć parzystość klucza 3DES. W końcu będę chciał przekonwertować nawet bajty na nieparzyste.

Dzięki, Dan

Answer 1

Chyba że to, co masz, nie jest wystarczająco szybkie, zachowaj to. Jest przejrzysty i zwięzły, a jego wydajność jest lepsza niż myślisz.

Będziemy odniesienia wszystko przeciwko odnośnika tablicy, najszybsza metoda testowałem:

ODD_PARITY = [ 
    false, 
    true, 
    true, 
    ... 
    true, 
    false, 
] 

def odd_parity?(hex_string) 
    ODD_PARITY[hex_string.to_i(16)] 
end 

• Array odnośnika oblicza parytet w wysokości 640.000 bajtów na sekundę.
• Kod C Bowsersenior oblicza parzystość z prędkością 640 000 bajtów na sekundę.
• Twój kod oblicza parzystość z szybkością 284 000 bajtów na sekundę.
• Natywny kod Bowsersenior oblicza parzystość z prędkością 171 000 bajtów na sekundę.
• Skrócony kod Theo oblicza parzystość z szybkością 128 000 bajtów na sekundę.

Answer 2

Prawdopodobnie tabeli odnośników tablicy z 255 wpisami byłyby najszybciej „Ruby” rozwiązania.

W C Zamaskowałem i przesunąłem. Lub jeśli mam SSE4, użyłbym instrukcji POPCNT z wbudowanym asemblerem. Jeśli potrzebujesz wysokiej wydajności, napisz rozszerzenie natywne w C, które wykonuje jedną z powyższych czynności.

http://en.wikipedia.org/wiki/SSE4

Answer 3

Brałeś spojrzeć na RubyDES library? To może usunąć potrzebę napisania własnej implementacji.

Aby obliczyć parzystości, można użyć coś jak następuje:

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 

Według prostych wskaźników, wersja inline C jest 3-4 razy szybciej niż natywna ruby ​​wersji

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 

Answer 4

x = 'AB'.to_i(16) 
p = 0 
until x == 0 
    p += x & 1 
    x = x >> 1 
end 
puts p # => 5 

można skrócić do

x = 'AB'.to_i(16) 
p = x & 1 
p += x & 1 until (x >>= 1) == 0 

jeśli chcesz czegoś, co jest nieczytelne ☺

Answer 5

Co powiesz na wykorzystanie oryginalnego rozwiązania z pamięcią? To będzie obliczać tylko raz dla każdej wartości całkowitej.

Answer 6

Chciałbym zbudować pojedynczą tabelę z 16 wpisami (jako tabelę 16-znakową), odpowiadającą każdemu półbajtowi (połowie) bajtów. Wpisy są 0,1,1,2,1,2 .... 4

Aby przetestować bajt,

Maska na lewym dziobanie i zrobić odnośnika, zapamiętywanie numeru. Do. przesuń w prawo o 4 i wykonaj drugie wyszukiwanie, dodając numer wyniku do poprzedniego, aby podać sumę.

Następnie przetestuj bit niskiego rzędu od sumy. Jeśli jest 1, bajt jest nieparzysty, jeśli jest równy 0, bajt jest parzysty. Jeśli wynik jest równy, odwracasz bit wyższego rzędu, używając instrukcji xor. Ta metoda wyszukiwania jest znacznie szybsza niż dodawanie bitów w bajcie na pojedyncze zmiany.

Wyślij do mnie wiadomość e-mail z prostą funkcją do wykonania parzystości dla 8 bajtów. 3DES używa 3 grup po 8 bajtów.