2
\$\begingroup\$

I'm creating a new data type, with the intention of overloading the arithmetic operators. It's for Galois Field arithmetic. The obvious thing to do is create a class, the instances of which will be the variables. There's precious little doc, the maths is a bit agricultural, incomplete and fragile at the moment, it might even be wrong in places, the lists will become ndarrays in time, but it's not those I want comments for, it's the use of the class setup method. I am also aware that there are Galois Field libraries out there, but I'm re-inventing the wheel because I want to know how one works.

Setting up the log tables in the class is most easily done at run time. As I want to set up different tables for different fields, my first thought was to create a metaclass, with which I could make a class for the target field size. However, I'm only about 2 notches above a noob, and reading the metaclass documentation left me cross-eyed, the metaclass PEPs likewise.

My next thought was to have the try/except in ____init___ run the setup function if the tables hadn't been generated, but that requires the field size be passed when creating a instance. I could do some things with defaults, and first-time-only tests, but they felt kludgy.

Then I reasoned that as a class is a first class object, functions defined on it can be called directly. I coded this up as a test, and it worked as expected. I think it's pretty clear, both the class code and the way to use it are obvious and unsurprising (if I can figure it out from first principles then it is obvious). However, I've not seen this form of structure referred to, let alone recommended anywhere.

Is it a known way to do things, or even safe? Is it a hack? I did see the @staticmethod decorator referred to in places, but this doesn't use it and still works, I am not sure it would add anything here. Should I be doing this in a very different way? I am sure there are more complicated ways to do it, but I'd prefer to stay this simple if there is no good reason to complicate.

class GF(object):
    """ implements Galois Field arithmetic for 2^4, 2^8 and 2^16
    overloads +, -, *, / and str() """

    def setup(g_power):
        if g_power not in (4, 8, 16):
            raise ValueError('cant do field size of {} yet'.format(g_power))
        GF.field_power = g_power
        GF.field_len = 1 << g_power
        GF.mask = GF.field_len-1
        GF.prim_poly = (0,0,0,0,9,0,0,0,29,0,0,0,0,0,0,0,32790)[g_power]

        GF.alogs = []
        GF.logs = [None]
        sr = 1

        for index in range(GF.field_len-1):
            GF.alogs.append(sr)
            sr <<= 1
            if sr&GF.field_len:
                sr ^= GF.prim_poly
            sr &= (GF.mask)

        for sr in range(1, GF.field_len):
            GF.logs.append(GF.alogs.index(sr))

    def __init__(self, n):
        try:
            self.value = n & GF.mask
        except AttributeError:
            raise RuntimeError('call GF.setup before making any instances of GF')      

    def __str__(self):
        return 'GF({}) element {:0>3d}d 0x{:0>2x}'.format(self.field_power, self.value, self.value)

    def __add__(self, other):
        if isinstance(other, GF):
            return(GF(self.value ^ other.value))
        else:
            raise TypeError('both args must be of GF type')

    def __sub__(self, other):
        return self+other

    def __mul__(self, other):
        if isinstance(other, GF):
            if self.value==0:
                return GF(0)
            if other.value==0:
                return GF(0)
            log_s = GF.logs[self.value]
            log_o = GF.logs[other.value]
            log_p = (log_s + log_o) % self.mask
            return GF(GF.alogs[log_p])
        else:
            raise TypeError('both args must be of GF type')

    def __truediv__(self, other):
        if isinstance(other, GF):
            if other.value==0:
                raise ValueError('cannot divide by 0')
            if self.value==0:
                return GF(0)
            log_s = GF.logs[self.value]
            log_o = GF.logs[other.value]
            log_p = (log_s - log_o) % self.mask   # always returns positive
            return GF(GF.alogs[log_p])
        else:
            raise TypeError('both args must be of GF type')

if __name__ == '__main__':

    GF.setup(8)

    print(GF(12)+GF(7))
    # test cases from the Intel paper
    print(GF(2)*GF(8))
    print(GF(18)*GF(5))
    print(GF(13)/GF(17))
    print(GF(2)/GF(11))
\$\endgroup\$
1
\$\begingroup\$

Defining a function inside a class create a staticmethod in Python 3 so you don't need to use staticmethod decorator. What you might want to use is classmethod to define a method which gets the class as first arguments. You code could be rewritten as:

class GP(object):

    @classmethod
    def setup(klass, g_power):

        # ... check for valid input

        # use klass instead of `GF`
        klass.field_power = g_power
        klass.field_len = 1 << g_power

It can be used just like a you do currently GP.setup(42). What changes is that you have a reference to the current class the consequence is that you can inherit class GP an call MyChildClass.setup which will will initialize MyChildClass and its namespace and not re-use the namespace of the parent class GP. If you need to inherit and need to have separate class properties (e.g. GP.field_power and GP.field_len) for each subclass, you will need to use classmethod decorator and rework your code to use klass like it's done in the above snippet and type(self) in the methods to access the properties of the correct class e.g. type(self).field_power instead of GP.field_power.

Regarding metaclass, it depends of your usecases. Here it seems like there is only few sets of classes that can be built given the GF class template because g_power can only be 4, 8 or 16. In this case metaclass or class decorators be a good fit.*

Using class decorators you end up writing the following code:

@setupGF(8)
class GF8(GF):
    pass

setupGF will takes klass argument and do the same things as you current GF.setup.

The metaclass method looks a bit different. You have to declare your class configuration upfront too, but with a class property:

class GF8(GF, metaclass=MetaGF):
    g_power = 8

But before showing the metaclass code, this can be used also without metaclass. Say you declare a class like that:

class GF8(GF):
    g_power = 8

You can conditionally call type(self).setup() when the class is not yet initialized. This can only work if you properly defined setup as a classmethod.

The metaclass will avoid the conditional call to the setup method. So it's in this case metaclass can be used as an optimisation.

The simplest way to define a metaclass is to use a function that will construct the final class and execute setup(g_power) code:

def MetaGF(name, bases, namespace):
    # construct class just like you would dynamically create a class
    klass = type(name, bases, namespace)
    # call setup
    setup_gf_class(klass.g_power)
    # return the initialized class
    return klass

class GF8(BaseGF, metaclass=MetaGF):
    g_power = 8

But if you have more important number of class that you must generate/configure at runtime you must take a more radical path using dynamic class construction:

class BaseGF(object):
    """ implements Galois Field arithmetic for 2^4, 2^8 and 2^16
    overloads +, -, *, / and str() """

    def __init__(self, n):
        self.value = n & type(self).mask

    def __str__(self):
        return 'GF({}) element {:0>3d}d 0x{:0>2x}'.format(
            self.field_power,
            self.value,
            self.value
        )

    def __add__(self, other):
        if isinstance(other, type(self)):
            return(type(self)(self.value ^ other.value))
        else:
            raise TypeError('both args must be of GF type')

    def __sub__(self, other):
        return self + other

    def __mul__(self, other):
        if isinstance(other, type(self)):
            if self.value == 0:
                return type(self)(0)
            if other.value == 0:
                return type(self)(0)
            log_s = type(self).logs[self.value]
            log_o = type(self).logs[other.value]
            log_p = (log_s + log_o) % self.mask
            return type(self)(type(self).alogs[log_p])
        else:
            raise TypeError('both args must be of the same GF type')

    def __truediv__(self, other):
        if isinstance(other, type(self)):
            if other.value == 0:
                raise ValueError('cannot divide by 0')
            if self.value == 0:
                return type(self)(0)
            log_s = type(self).logs[self.value]
            log_o = type(self).logs[other.value]
            log_p = (log_s - log_o) % self.mask   # always returns positive
            return type(self)(type(self).alogs[log_p])
        else:
            raise TypeError('both args must be of the same GF type')


def MetaGF(g_power):
    name = 'GF(%s)' % g_power
    GF = type(name, (BaseGF,), dict())

    if g_power not in (4, 8, 16):
        raise ValueError('cant do field size of {} yet'.format(g_power))

    GF.field_power = g_power
    GF.field_len = 1 << g_power
    GF.mask = GF.field_len-1
    GF.prim_poly = (0, 0, 0, 0, 9, 0, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 32790)[g_power]

    GF.alogs = []
    GF.logs = [None]
    sr = 1

    for index in range(GF.field_len-1):
        GF.alogs.append(sr)
        sr <<= 1
        if sr & GF.field_len:
            sr ^= GF.prim_poly
        sr &= (GF.mask)

    for sr in range(1, GF.field_len):
        GF.logs.append(GF.alogs.index(sr))

    return GF


GF8 = MetaGF(8)

print(GF8(12)+GF8(7))

# test cases from the Intel paper
print(GF8(2)*GF8(8))
print(GF8(18)*GF8(5))
print(GF8(13)/GF8(17))
print(GF8(2)/GF8(11))

This approach can also works in the other cases an is kind of the simpler both to use and to understand since it's only basic function calls. It's my prefered solution.

Have a look at How can I dynamically create derived classes from a base class for more information on how dynamic class creation works.

\$\endgroup\$
7
  • \$\begingroup\$ Obviously I need to do a lot more reading, and probably solving some bigger problems that need it, before I understand what advantage this extra complexity gives me, other than obscure the function of the code. \$\endgroup\$ – Neil_UK Sep 12 '15 at 16:08
  • \$\begingroup\$ Fore me they are the following paths 0) keep the code as is 1) use classmethod and class decorator 2) use metaclass 3) use dynamic class construction. I recommend you go with 1) if you a have few GF class. This is the most responsible thing. Class decorators are always recommended instead of metaclass, and look like function decorator so that knowledge you can directly re-use. Otherwise 3, which simply constructing a class at runtime. Tell me what sound obscure I will improve the answer. \$\endgroup\$ – amirouche Sep 12 '15 at 18:23
  • \$\begingroup\$ @user44635 what do you think of the last solution that use GF8 = MetaGF(8) to generate a GF with g_power=8? \$\endgroup\$ – amirouche Sep 12 '15 at 18:29
  • \$\begingroup\$ My main question is - that for my use case, is there anything wrong with what I have done, sufficiently wrong that it needs to be altered, is discouraged by a PEP, or might break in a future version of python? \$\endgroup\$ – Neil_UK Sep 12 '15 at 20:43
  • 1
    \$\begingroup\$ of the options, GF8 = MetaGF(8) seems the sensible way to do it, but the metaclass doesn't seems to generate a class as an instance of the metaclass, like a class generates an object as an instance of the class. I was trying to read the metaclass docs with that prior assumption, so obviously didn't find what I was looking for. \$\endgroup\$ – Neil_UK Sep 12 '15 at 20:54
0
\$\begingroup\$

Thanks to this forum, and especially amirouche for listening and helping while I painfully learned. As ever, understand the real requirement before trying to fix up trial solutions.

What do I actually want?
a) A module, that can be imported
b) that implements Galois Field arithmetic
c) that is fast to load, i.e. as lazy as possible creating lookup tables
d) that requires minimum or no setup in use, ideally exporting the actual classes
e) and DRY as much as possible
f) where classes for new field sizes can be added to the module later in an error-free and pain-free way

I think I've finally got my importable module, and learned a bit more about classes and namespaces in the process.

The key was using the right namespace in the base class. To have a base class used in multiple derived classes, yet able to override operators and modify class rather than instance properties. It was not knowing how to do this that led to the trial solution of the original question. At least the setup(self) function now looks familiar as it's called on the instance and defined with (self).

The prototype base class from amirouche used type(self) everywhere in the base class. I've modified it to use type(self) only where writing, and self where reading, I think that's clearer stylistically?

In my first attempt, now commented out, I used the type(name,bases,dict) form for the derived classes, before realising that it was now just the standard pattern.

""" Module GF - 2^4 and 2^8 Galois Field classes """

class BaseGF(object):
    """ implements Galois Field arithmetic 
    overloads +, -, *, / and str() """

    def __init__(self, n):
        print('running __init__ in {}'.format(self.F_POWER))
        self.value = n & self.F_MASK

    def __str__(self):       
        return 'GF{} element {}'.format(self.F_POWER, self.value)

    def __add__(self, other):
        if isinstance(other, type(self)):        
            return(type(self)(self.value ^ other.value))
        else:
            raise TypeError('both args must be of same GF type')

    def __mul__(self, other):
        if isinstance(other, type(self)):        
            if self.value == 0:
                return type(self)(0)        
            if other.value == 0:
                return type(self)(0)
            try:                
                log_s = self.logs[self.value]
            except AttributeError:
                self.setup()
                log_s = self.logs[self.value]                
            log_o = self.logs[other.value]
            log_p = (log_s + log_o) % self.F_MASK
            return type(self)(self.alogs[log_p])
        else:
            raise TypeError('both args must be of the same GF type')

    def setup(self):
        print('setting up log tables')
        type(self).alogs = []
        type(self).logs = [None]
        sr = 1

        for index in range(self.F_LENGTH-1):
            type(self).alogs.append(sr)
            sr <<= 1
            if sr & self.F_LENGTH:
                sr ^= self.F_PRIM_POLY
            sr &= self.F_MASK

        for sr in range(1, self.F_LENGTH):
            type(self).logs.append(self.alogs.index(sr))

"""
GF8 = type('GF8', (BaseGF,),
           {'F_POWER':8,
            'F_LENGTH':256,
            'F_MASK':255,
            'F_PRIM_POLY':29})
"""

class GF8(BaseGF):
    F_POWER = 8
    F_LENGTH = 256
    F_MASK = 255
    F_PRIM_POLY = 29

class GF4(BaseGF):
    F_POWER = 4
    F_LENGTH = 16
    F_MASK = 15
    F_PRIM_POLY = 9

def make_GFn(f_power, f_prim_poly):
    """ return an arbitrary binary Galois Field class """
    name = 'GFn{}'.format(f_power)
    return type(name, (BaseGF,), {'F_POWER':f_power,
                                  'F_LENGTH':(1<<f_power),
                                  'F_MASK':((1<<f_power)-1),
                                  'F_PRIM_POLY':f_prim_poly})




if __name__=='__main__':

    GF88 = make_GFn(8, 29)
    print(GF88.__name__)

    print('create objects')
    a = GF8(7)
    b = GF8(12)
    c = GF4(3)
    print(a)

    print('add')
    print(a+b)

    print('multiply')
    print(a*b)

    print('multiply again')
    print(a*b)

    print('add between different fields')
    print(a+c)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.