ISCN.py

# -*- coding:Latin-1 -*-
# Ce programme, premier essai en python donc Èventuellement quelques "singularitÈs", 
# a pour but de vÈrifier et tester les algorithmes de codage et dÈcodage des ISCNs.
# Ces Algorithmes peuvent bien sur Ítre grandement optimisÈs une fois les choix de 
# nombres de segments max et nombres d'octets max faits
from math import *
from random import *

# Structs est la fonction qui retourne le nombre de structures ‡ i segments sur un 
# identifiant ‡ p octets.
# Ou Ègalement bien s˚r, le nombre de structures ‡ i segments sur un identifiant ‡ p bits.
# note: le nombre de structure ‡ 0 segment sur p octets est 1
def Structs (i,p ):
    if i==1 or i==0 :
        return 1
    elif i==2:
        return p-1
    elif i==3:
        return ((p-1)*(p-2))//2
    elif i==4:
        return ((p-1)*(p-2)*(p-3))//6
    elif i==5:
        return ((p-1)*(p-2)*(p-3)*(p-4))//24
    elif i==6:
        return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5))//120
    elif i==7:
        return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5)*(p-6))//720
    elif i==8:
        return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5)*(p-6)*(p-7))//5040
    else:
        print "i is out of range in Structs, value : " , i

# STs est la fonction qui retourne le nombre total de structures ‡ i ou moins segments 
# dans p octets, 
# y compris la structure vide (ou ‡ 0 segment) qui compte pour une structure.
# cette fonction ‡ rÈÈcrire directement en polynomes
def STs (i,p):
    j=1
    r=1
    while j <= i :
        k=j
        while k <= p :
           r += Structs (j,k)
           k+=1
        j+=1
    return r
    
#tOc retourne la taille minimale en octets pour coder l'entier i
def tOc (i) :
    if (i==0 or i==1) : 
        return 1
    else:
        return int(log(i,2))//8+1
    
# AlgCodage prend en input une liste ls de tailles de segments, et retourne le numÈro de 
# structure correspondant. 
# Ceci pour un nombre de segments max MS et une taille d'octets max P. 
# Idstr est l'offset du numÈro de structure dans les appels rÈcursifs.
# Le principe est d'incrÈmenter Idstr avec les structures ‡ taille de premier segment 
# infÈrieur ‡ celle considÈrÈe, 
# puis appelrÈcursif sur le deuxiËme segment une fois positionÈ dans le bon intervalle.
ls=[]
def AlgCodage (ls , MS , P, Idstr=0):
    ll=len(ls)
    lseg1=0
    pos=0
    i=0
    if ll==0:
        return Idstr
    else :
        lseg1=ls[0]
        while i<lseg1:
            if i==0 : Idstr=Idstr+1
            else : Idstr=Idstr+STs(MS-1,P-i)
            i+=1
        del ls[0]
        return AlgCodage(ls,MS-1,P-lseg1,Idstr)
        
            
# AlgDecodage prend en input un numÈro de structure, et renvoi la liste de tailles de segments 
# correspondante. 
# Ceci pour un nombre max de segments MS et un nombre max d'octets P
ls=[]
def AlgDecodage (Idstr, ls, MS, P):
    lseg1=0 #taille premier segement courant
    pos=0
    if Idstr==0 : return ls
    while True:
        if lseg1==0 : pos=pos+1 
        else : pos=pos+STs(MS-1,P-lseg1)
        if Idstr>=pos : 
            int1=pos
            lseg1+=1
        else : break
    ls.append(lseg1)
    return AlgDecodage(Idstr-int1,ls,MS-1,P-lseg1)


def pAD (i,j):
    k=i
    while k<=j:
        ps(k)
        k+=1
    return None

def ps (k):
    print "str", k , AlgDecodage(k,[],7,14)
    return None

def ps12 (k):
    print "str", k , AlgDecodage(k,[],3,5)
    return None
    

# CodeListInt prend une liste d'entier en entrÈe et la transforme en un entier (binaire),
# avec le code de structure au dÈbut et ensuite les entiers
# Note : nous avons fixÈ ici le nombre de segments max ‡ 7 et le nombre d'octets max ‡ 14 
# pour les entiers (16 en tout), ie 128 bits, 
# la structure est codÈe sur 16 bits, 14 suffiraient
lint=[]
def CodeListInt (lint):
     ll=len(lint)
     lo=list(lint)
     i=0
     to=0
     while i<ll :
         t=tOc(lint[i])
         lint[i]=t
         to=to+t
         i+=1
     if to>14 :
         print "overflow", to
         return to
     lt=list(lint)
     nstruct=AlgCodage(lint,7,14)
     i=0
     bint=nstruct
     offset=16
     while i<ll :
        bint=bint | lo[i]<<offset
        offset=offset + 8*lt[i]
        i+=1  
     return bint

def mmask (p):
    ones=255 
    return ones<<8*(p-1)

# DecodeListInt prend un entier ou numÈro ISCN "empaquetÈ" et renvoi la liste d'entiers 
# correspondante
def DecodeListInt (intg):
    mask=mmask(1)|mmask(2)
    nstruct= intg & mask
    intg=intg>>16
    ls=AlgDecodage(nstruct, [],7, 14)
    ll=len(ls)
    lint=[]
    i=0
    off=0
    while i<ll : 
        mask=0
        k=0
        while k<ls[i] :
            mask= mask | mmask(k+1)
            k+=1
        lint.append((intg & (mask<<(off*8)))>>off*8)
        off=off+ls[i]
        i+=1
    return lint    
        

#Test de Code et Decode pour ms=7, n tests sont effectuÈs
def test (n):
    i=1
    lint=[]
    lseg=[]
    while i<=n:
        l=randrange(1,8)
        mo=14
        k=1
        while k<=l :
            tseg=randrange(1,mo-(l-k))
            lseg.append(tseg)
            mo=mo-tseg
            lint.append(randrange(pow(2,tseg*8)))
            k+=1
        i+=1
        olint=list(lint)
        bint=CodeListInt(lint)
        dlint=DecodeListInt(bint)
        if cmp(olint,dlint)!=0:
            printh(olint)
            print lseg
            print hex(bint)
            print hex(bint>>16)
            printh(dlint)
            return False
        lint=[]
        lseg=[]
    return True

#affichage hexadÈcimal d'une liste pour les tests       
def printh (l):
    print "[",
    for n in l :
        print hex(n), "," ,
    else : print "]"
        
        
        
#Les fonctions ci dessous implÈmentent les fonctions Dj(p) et TDj(p)
#de la mÈthode ou solution 2
def D1(p):
    return 1

def D2(p):
    if p<2:
        print "D2 error" , p
    else:
        return p-1

def D3(p):
    r=0
    if p<3:
        print "D3 error" , p
    else :
        i=1
        while i <= p-2:
            r+=D2(p-i)
            i+=1
        return r

def D4(p):
    r=0
    if p<4:
        print "D4 error" , p
    else :
        i=1
        while i <= p-3:
            r+=D3(p-i)
            i+=1
        return r
            
def D5(p):
    r=0
    if p<5:
        print "D5 error" , p
    else :
        i=1
        while i <= p-4:
            r+=D4(p-i)
            i+=1
        return r

def D6(p):
    r=0
    if p<6:
        print "D6 error" , p
    else :
        i=1
        while i <= p-5:
            r+=D5(p-i)
            i+=1
        return r
    
def D7(p):
    r=0
    if p<7:
        print "D7 error" , p
    else :
        i=1
        while i <= p-6:
            r+=D6(p-i)
            i+=1
        return r
    

def TD5(p):
    return D1(p)+D2(p)+D3(p)+D4(p)+D5(p)    

def TD7(p):
    return D1(p)+D2(p)+D3(p)+D4(p)+D5(p)+D6(p)+D7(p)