# -*- 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)
WordPress:
J’aime chargement…
Initiative ISCN ? 