FBlag

#!/usr/bin/python3

# select chunks from infile.png and write them resorted to outfile.png

# usage: png_resort.py <infile.png> <outfile.png>
# user input:
#   comma separated list of chunk indices or index ranges
#     p.ex.: 0,2..4,1,5
#   or 'exit'

# Literature
# ----------
# Portable Network Graphics (PNG) Specification (Second Edition)

import readline,struct,sys,zlib # drop readline for less dependencies and comfort
from functools import *
from io import *



png_signature = b'\x89\x50\x4e\x47\x0d\x0a\x1a\x0a'


def print_error(*msgs):
        """print highlighted error message(s)"""

        msgs = ' '.join(map(str,msgs))
        print('\033[1;31m[Error] {0}\033[1;m'.format(msgs))


def test(title,condition,val=None):
        """test condition, if false print test title and (maybe) val"""

        if condition: return True
        else:
                s = 'Test failed: {0} ({1})'.format(title,s) if val else 'Test failed: {0}'.format(title)
                print_error(s)
                return False


def check_png_signature(f):
        """read and validate png file signature"""

        # file signature (5.2)
        sig = f.read(8)

        return \
                test('signature length',len(sig) == 8) and \
                test('signature',sig == png_signature)


def is_png_uint32(val):
        # (7.1)
        return 0 <= val < 2**31


def png_chunks(f):
        """file -> [{'type','pos','length'[,'crc']}]"""

        # chunk layout (5.3)
        # +-------------------------------------------------+
        # | length (4) | type (4) | data (length) | crc (4) |
        # +-------------------------------------------------+

        def read_bytes(name,length):
                """read length bytes"""
                val = f.read(length)

                if len(val) < length:
                        print_error('{0} < {1}'.format(name,length))
                        raise ValueError
                else: return val


        ret = []
        cnt = 0

        print('No. Type (Position,Length)\n'+'-'*26)
        while True:
                # read chunk
                pos = f.tell()
                length_ = f.read(4)
                if len(length_) == 4:
                        (length,) = struct.unpack_from('!I',length_,0)
                        try:
                                type_ = read_bytes('chunk type',4)
                                data  = read_bytes('chunk data',length) if length > 0 else b''
                                crc__ = read_bytes('chunk crc',4)
                        except:
                                print_error('defective chunk')
                                break
                        else:
                                type = ''
                                try:
                                        type = type_.decode('ascii')
                                except:
                                        print_error('non-ascii characters in type')
                                        type = type_.decode('ascii','replace')

                                (crc_,) = struct.unpack_from('!I',crc__,0)
                                zcrc = zlib.crc32(type_+data)
                                crc = crc_ == zcrc

                                chunk_attrs = {'type':type,'pos':pos,'length':length+12}

                                # (5.1)
                                test('chunk length limit',is_png_uint32(length),length)
                                # check crc and repair
                                if not test('chunk crc',crc,crc):
                                        while True:
                                                c = input('repair crc [y|n]:').strip().lower()
                                                if c == 'y':
                                                        chunk_attrs['crc'] = struct.pack('!I',zcrc)
                                                        break
                                                elif c == 'n': break
                                                else: print_error("wrong input, just y or n")

                                ret.append(chunk_attrs)
                                print('{3:>2}. {0} ({1},{2})'.format(type,pos,length+12,cnt))
                                cnt += 1
                # eof
                elif len(length_) == 0: break
                # error
                else:
                        print_error('defective chunk length')
                        break

        return ret


def order_from_string(s):
        """create list of numbers from string s"""

        err = False

        def convert(si):
                nonlocal err

                if si == '': return []

                try:
                        # simple integer conversion
                        i = int(si)
                except:
                        # range notation
                        try:
                                a,b = si.split('..')
                                c,d = int(a),int(b)
                                l   = []
                                if c < d:
                                        l = list(range(c,d+1))
                                else:
                                        l = list(range(d,c+1))
                                        l.reverse()
                        except:
                                print_error('unknown representation:',si)
                                err = True
                                return []
                        else: return l
                else: return [i]


        order = reduce(lambda x,i:x+convert(i),s.strip().split(','),[])

        return order if not err else None



if __name__ == '__main__':
        # command line arguments
        if len(sys.argv) != 3:
                print_error('Incorrect number of arguments.\n' \
                        'usage: png_resort.py <infile.png> <outfile.png>')
                exit(1)

        try:
                # read file
                infile_name = sys.argv[1]
                print('\033[1;32mFile: {0}\033[1;m'.format(infile_name))
                with open(infile_name,'rb') as infile:
                        # read signature
                        check_png_signature(infile)

                        # read chunks
                        chunks = png_chunks(infile)
                        if len(chunks) == 0: exit(0)

                        # ask for new order
                        while True:
                                cmd = input('Enter new order (p.ex.: 0,3..5,2): ')
                                cmd = cmd.strip()
                                if cmd == 'exit': exit(0)

                                order = order_from_string(cmd)
                                if order == None: continue
                                print('New order: {0}'.format(order))

                                # check new order
                                if not reduce(lambda b,v: b and 0 <= v < len(chunks),order,True):
                                        print_error('unknown chunk indices in new order')
                                else: break

                        # write new file
                        outfile_name = sys.argv[2]
                        with open(outfile_name,'wb') as outfile:
                                # write signature
                                outfile.write(png_signature)

                                # write chunks
                                for chunk_no in order:
                                        c = chunks[chunk_no]
                                        infile.seek(c['pos'],SEEK_SET)
                                        # !!! needs advanced buffering for big files
                                        data = infile.read(c['length'])
                                        data = data if 'crc' not in c else data[:-4]+c['crc']
                                        written = outfile.write(data)
                                        if not c['length'] == len(data) == written:
                                                print_error('copy error')
                                                exit(1)

        except IOError as err:
                print_error(err)
                exit(1)

        exit(0)
 

#!/usr/bin/python3

# Implementation of the MIN-INCR ICDFA minimisation algorithm without(!)
# optimized data structures.
#
# Use minimalIncremental() from FAdo Project for your projects.


# Literature
# ----------
#
# [idm] Almeida, Moreira, Reis: Incremental DFA minimisation
# [ufa] Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm
#
#
# Links
# -----
#
# FAdo Project:
#   - http://www.ncc.up.pt/FAdo/
#   - http://fado.dcc.fc.up.pt/FAdo/


verbose = False



# ==== fake union-find ==== ([ufa])

sets = {}

def make(x):
        """creates new singleton set {x}"""
        global sets

        sets[x] = set([x])

def find_(sets,x):
        """returns representative element of set containing x"""

        for id,s in sets.items():
                if x in s:
                        return id

def find(x):
        """wrapper for find_"""
        global sets

        return find_(sets,x)

def union(p,q):
        """combines a and b"""
        global sets

        a,b = normalise(find(p),find(q))
        if a != b:
                sets[a] |= sets[b]
                del sets[b]



# ==== minimisation ==== ([idm])

neq   = set()
equiv = set()
path  = set()
dfa   = {}

# (idm L1.1)
def normalise(p,q):
        return (p,q) if p<q else (q,p)


# (idm L1.4) - just use python's set implementation
def set_make():
        return set()

def set_insert(v,s):
        s.add(v)

def set_remove(v,s):
        s.remove(v)

def set_search(v,s):
        return v in s

def set_elements(s):
        return s


# (idm L1.3)
def equiv_p(p,q):
        """tests equivalence of p and q"""
        global neq, equiv, path, dfa, verbose
        d = dfa

        print_("equiv: {0}\npath : {1}\nneq  : {2}\n".format(equiv,path,neq))

        if (p,q) in neq:
                return False

        if set_search((p,q),path):
                return True

        set_insert((p,q),path)

        for a in d['Sigma']:
                print_("p,a,q:",p,a,q)

                (p_,q_) = normalise(find(d['delta'](p,a)),find(d['delta'](q,a)))

                if p_ != q_ and not set_search((p_,q_),equiv):
                        set_insert((p_,q_),equiv)

                        if not equiv_p(p_,q_):
                                return False
                        else:
                                set_remove((p_,q_),path)

        set_insert((p,q),equiv)

        return True


# (idm Theorem 2)
def joinstates(d,classes):
        """returns new dfa based on equivalence classes"""

        Q = set(classes.keys())
        Sigma = d['Sigma']
        delta = lambda p,a: find_(classes,d['delta'](p,a))
        q0 = find_(classes,d['q0'])
        F = set(map(lambda x: find_(classes,x),list(d['F'])))

        return {'Q':Q,'Sigma':Sigma,'delta':delta,'q0':q0,'F':F}


# (idm L1.2)
def min_incr(d):
        global neq, equiv, path, dfa
        dfa = d

        for q in d['Q']:
                make(q)

        neq = set([normalise(p,q) for p in d['F'] for q in d['Q'] - d['F']])

        for p in d['Q']:
                for q in [x for x in d['Q'] if x > p]:
                        if (p,q) in neq:
                                continue

                        if find(p) == find(q):
                                continue

                        equiv = set_make()
                        path  = set_make()

                        if equiv_p(p,q):
                                for (p_,q_) in set_elements(equiv):
                                        union(p_,q_)
                        else:
                                neq |= path

        classes = {}
        for p in d['Q']:
                lider = find(p)
                classes[lider] = classes[lider] | set([p]) if lider in classes else set([p])

        print_('classes:',classes,'\n')

        return joinstates(d,classes)



# ==== I/O ====

def print_(*args):
        global verbose

        if verbose:
                print(*args)

def print_dfa(name,d):
        print('{0}\n{1}'.format(name,'='*len(name)))
        print('Q    : {0}\nSigma: {1}\ndelta:'.format(d['Q'],d['Sigma']))
        for q,a in [(q,a) for q in d['Q'] for a in d['Sigma']]:
                print(' '*6,q,a,d['delta'](q,a))
        print('q0   : {0}\nF    : {1}\n'.format(d['q0'],d['F']))



# ==== examples ====

# DFA d={q,s,d,q0,f}

def dfa_01_d(p,a):
        tab = {
                0:{'a':1,'b':2},
                1:{'a':4,'b':2},
                2:{'a':3,'b':2},
                3:{'a':4,'b':0},
                4:{'a':4,'b':4}}

        return tab[p][a]

dfa_01 = {'Q':set([0,1,2,3,4]),'Sigma':set(['a','b']),'delta':dfa_01_d,'q0':0,'F':set([4])}


def dfa_02_d(p,a):
        tab = {
                0:{'a':1,'b':4},
                1:{'a':2,'b':5},
                2:{'a':3,'b':2},
                3:{'a':3,'b':2},
                4:{'a':5,'b':0},
                5:{'a':4,'b':1}}

        return tab[p][a]

dfa_02 = {'Q':set(range(0,6)),'Sigma':set(['a','b']),'delta':dfa_02_d,'q0':0,'F':set([2,3,4])}


# ==== main ====

if __name__ == '__main__':
        print_dfa('DFA 01',dfa_01)
        dfa_01_min = min_incr(dfa_01)
        print_dfa('DFA 01 min',dfa_01_min)

        print_dfa('DFA 02',dfa_02)
        dfa_02_min = min_incr(dfa_02)
        print_dfa('DFA 02 min',dfa_02_min)