def _chien_search_fast(self, sigma):
        '''Real chien search, we reuse the previous polynomial evaluation and just multiply by a constant polynomial. This should be faster, but it seems it's just the same speed as the other bruteforce version. However, it should easily be parallelizable.'''
        # TODO: doesn't work when fcr is different than 1 (X values are incorrectly "shifted"...)
        # TODO: try to mix this approach with the optimized walk on only interesting values, implemented in _chien_search_faster()
        X = []
        j = []
        p = GF2int(self.generator)
        if not hasattr(self, 'const_poly'): self.const_poly = [GF2int(self.generator)**(i+self.fcr) for i in _range(self.gf2_charac, -1, -1)] # constant polynomial that will allow us to update the previous polynomial evaluation to get the next one
        const_poly = self.const_poly # caching for more efficiency since it never changes
        ev_poly, ev = sigma.evaluate_array( p**1 ) # compute the first polynomial evaluation
        # Try for each possible location
        for l in _range(1, self.gf2_charac+1): # range 1:256 is important: if you use range 0:255, if the last byte of the ecc symbols is corrupted, it won't be correctable! You need to use the range 1,256 to include this last byte.
            #l = (i+self.fcr)

            # Check if it's a root for the polynomial
            if ev == 0: # If it's 0, then bingo! It's an error location
                # Compute the error location polynomial X (will be directly used to compute the errors magnitudes inside the Forney algorithm)
                X.append( p**(-l) )
                # Compute the coefficient position (not the error position, it's actually the reverse: we compute the degree of the term where the error is located. To get the error position, just compute n-1-j).
                # This is different than the notes, I think the notes were in error
                # Notes said j values were just l, when it's actually 255-l
                j.append(self.gf2_charac - l)

            # Update the polynomial evaluation for the next iteration
            # we simply multiply each term[k] with alpha^k (where here alpha = p = GF2int(generator)).
            # For more info, see the presentation by Andrew Brown, or this one: http://web.ntpu.edu.tw/~yshan/BCH_decoding.pdf
            # TODO: parallelize this loop
            for i in _range(1, len(ev_poly)+1): # TODO: maybe the fcr != 1 fix should be put here?
                ev_poly[-i] *= const_poly[-i]
            # Compute the new evaluation by just summing
            ev = sum(ev_poly)

        return X, j
def _chien_search_fast ( self , sigma ) : X = [ ] j = [ ] p = GF2int ( self . generator ) if not hasattr ( self , 'const_poly' ) : self . const_poly = [ GF2int ( self . generator ) ** ( i + self . fcr ) for i in _range ( self . gf2_charac , - 1 , - 1 ) ] const_poly = self . const_poly ev_poly , ev = sigma . evaluate_array ( p ** 1 ) for l in _range ( 1 , self . gf2_charac + 1 ) : if ev == 0 : X . append ( p ** ( - l ) ) j . append ( self . gf2_charac - l ) for i in _range ( 1 , len ( ev_poly ) + 1 ) : ev_poly [ - i ] *= const_poly [ - i ] ev = sum ( ev_poly ) return X , j
Real chien search, we reuse the previous polynomial evaluation and just multiply by a constant polynomial. This should be faster, but it seems it's just the same speed as the other bruteforce version. However, it should easily be parallelizable.