user.p0d.org

bits release in progress

Algorithms, snippets

Tags python, algo

IPv4 addresses manipulations

Note

Python power operator are ** and pow; most other languages will use ^.

Best IP class ever: http://pypi.python.org/pypi/IPy/

# iptolong
# For IP: a.b.c.d
ipquad, mask = '127.0.0.1/32'.split('/')
iplong = a*256^3 + b*256^2 + c*256^1 + d
iplong = reduce(lambda a,b: long(a)*256 + long(b), ipquad.split('.'))

masklong = 2L**mask -1
hostlong = iplong & mask
netlong  = iplong - hostlong

iplonghex = ''.join(["%02X" % long(i) for i in ipquad.split('.')])
iplong = long(iplonghex, 16)
ipquad = '%d.%d.%d.%d' % (
   (iplong >> 24) & 0xFF,
   (iplong >> 16) & 0xFF,
   (iplong >> 8) & 0xFF,
   iplong & 0xFF
)

# iplong signed integer
iplong_si = int(((iplong & 0x7fffffff) + ((iplong & 0x80000000) >> 31)) \
   * (-((iplong & 0x80000000) >> 30) + 1))

# last ip of a CIDR
hostmask = (1<<(32-mask))-1
iplonglast = iplong | hostmask

Signed and unsigned integer conversion, in Python

Convert an unsigned in a signed representation.

def sign_and_magnitude(x):
   for x in (0,1,127,128,255):
      print ((x & 0x7f) * ((-1,1)[(x & 0x80)==0]))

def sign(u, bits=8):
   '''(((u & 0x7f) + ((u & 0x80) >> 7)) * (-((u & 0x80) >> 6) + 1))'''
   m = 1<<bits
   H = m>>1
   h = H-1
   return (((u & h) + ((u & H) >> bits-1)) * (-((u & H) >> bits-2) + 1))

def uint2int(uint):
   '''Convert an unsigned 32 bits int "uint" to it's signed equivalent.'''
   return int(((uint & 0x7fffffff) + ((uint & 0x80000000) >> 31)) \
      * (-((uint & 0x80000000) >> 30) + 1))

# code a verifier
def int2uint(int):
   '''Convert a signed 32 bits int "int" to it's unsigned equivalent.'''
   if int >= 0:
      return int
   return (int & 0x7FFFFFFF) - ((int << 1) + 1)

Sizeof for a number of an arbitrary base

Author:Maz
Date:2008-06-26 14:19 -0400

A technique to determine the number of bytes occupied by a number whatever the basis is could be:

for (octets = 0; (num != 0); ++octets) num /= base;

Or in Python:

def f(num, base=10):
   o = 0
   while num:
      o+= 1
      num/= base
   return o

def bitLen(int_type): # from http://wiki.python.org/moin/BitManipulation
   length = 0
   while (int_type):
      int_type >>= 1
      length += 1
   return(length)

Convertir un nombre vers une base determinee par un tableau:

def base(i, b):
   '''
   >>> import string
   >>> array = string.digits + string.lowercase + string.uppercase
   >>> base(0xffff, array[:16])
   'ffff'
   >>> base(0xffff, array[:36])
   '1ekf'
   '''
   l, d = len(b), []
   while i:
      d.append(b[i%l])
      i/= l
   d.reverse()
   return ''.join(d)

def unbase(s, b):
   '''
   >>> import string
   >>> array = string.digits + string.lowercase + string.uppercase
   >>> unbase('ffff', array[:16])
   65535
   >>> unbase('1ekf', array[:36])
   65535
   '''
   l, d = len(b), 0
   for i, c in enumerate(s[::-1]):
      d+= b.index(c) * (l**i)
   return d

Binary prefix

def binary_prefix(value, binary=True):
   '''Return a tuple with a scaled down version of value and it's binary prefix

   Parameters:
   - `value`: numeric type to trim down
   - `binary`: use binary (ICE) or decimal (SI) prefix

   Usage::
   >>> ['%.2f %sB' % binary_prefix(nbr)
      for nbr in (12, 1023, 1028, 4096, 1<<16, 1<<32, 1<<128)]
   ['12.00 B', '1023.00 B', '1.00 KiB', '4.00 KiB', '64.00 KiB', '4.00 GiB',
   '274877906944.00 YiB']
   >>> [k % binary_prefix(v, False) for k,v in {
      'modem %u %s':56000, 'SATA %u %sb/s':3*10**9,
      'Ethernet %u%sb/s': 10**7, 'income %.1f %s EUR':-7**8
      }.iteritems()]
   ['income -5.8 M EUR', 'modem 56 k', 'SATA 3 Gb/s', 'Ethernet 10Mb/s']
   '''
   SI = 'kMGTPEZY'
   unit = 1024. if binary else 1000.
   for i in range(-1, len(SI)):
      if abs(value) < unit:
         break
      value/= unit
   return (value, '' if i<0 else (SI[i].upper() + 'i' if binary else SI[i]))

Regular expressions

Extract all URI

Note

For an HTML document, prefix with (?:[hH][rR][eE][fF]=['"]?)( ... ).

re.compile(
        r'''[a-zA-Z]+:/{,3}[%s]+/?[%s]*|%s''' %(
        r'A-Za-z0-9\-\.',
        r'\%\;\/\?\:\@\&\=\+\$\,\[\]A-Za-z0-9\-_\.\!\~\*\'\(\)\w#',
        r'\%\;\/\?\:\@\&\=\+\$\,\[\]A-Za-z0-9\-_\.\!\~\*\'\(\)'
))
Validate an email address with a regexp

See emailaddr.re.


Benchmarks in Python

With a function or decorator
import time
def bench(func):
   def wrap(*args, **kwargs):
      t = time.time()
      r = func(*args, **kwargs)
      print '%s: %f' % (func.__name__, time.time()-t)
      return r
   return wrap
# usage
>>> def foo(m): print m
>>> bench(foo)(m=42)

# variant
>>> @bench
>>> def foo(m): print m
>>> foo(42)
With timeit

In Python2.3:

/usr/lib/python2.3/timeit.py "import myscript"

In Python2.5:

python -m timeit 'import myscript;myscript.run()'

Sorting, in Python

From http://code.activestate.com/recipes/577679/#c3:

def natkey(s):
    if s == "":
        return [""]
    parts = []
    part = ""
    numberMode = False
    for c in s:
        if c.isdigit() ^ numberMode:
            if numberMode:
                part = int(part)
            parts.append(part)
            part = c
            numberMode = not numberMode
        else:
            part += c
    if numberMode:
        part = int(part)
    parts.append(part)
    return parts

Unicode and utf-8 in Python

import codecs
import sys
sys.stdin  = codecs.getreader("utf-8")(sys.stdin)
sys.stdout = codecs.getwriter("utf-8")(sys.stdout)

Color

Sources:

Color brightness is determined by the following formula:

((Red * 299) + (Green * 587) + (Blue * 114)) / 1000

Color difference is determined by the following formula:

a = 0x33, 0x66, 0xcc
b = 0x85, 0x4f, 0x61
Red,Green,Blue = zip(a,b)
(max(Red) - min(Red)) + (max(Green) - min(Green)) + (max(Blue) - min(Blue))

Loop around an array

Convert a weekdays array numbered as in ISO 8601 to any style:

ISO_WEEK  = ('Mo', 'Tu', 'We', 'Th', 'Fr', 'Sa', 'Su')
FIRST_DAY = 0 # 0 for sunday, 1 for monday, 2 for tuesday, ...
WEEK = [ISO_WEEK[ (i-1+FIRST_DAY) % 7 ] for i in range(7)]

Logical gate

Simplify: if ((year and month and day) or (year and month) or (year)):

if (year and (month or not day)) # Python
if (year && (month || !day))     # C
if (year & (month | ~day))       # binary operation

Simplify: if ((argc == 3 and argv[2] != "zc") or (argc != 2)):

if ((argc == 3 && !argv[2] != "zc") ^ argc == 2)

Haversine formula

Compute the distance between two conjugate graticules.

from math import asin, sqrt, sin, cos, pi
R  = 3956         # earth radius
PI = pi/180       # π must be in radians

def distance(src, dst):
   assert type(src) is tuple and len(src) == 2 \
      and type(src[0]) == type(src[1]) == float
   assert type(dst) is tuple and len(dst) == 2 \
      and type(dst[0]) == type(dst[1]) == float

   return R * 2 * asin(
      sqrt(
         sin((src[0] - abs(dst[0])) * pr / 2) ** 2 +
         cos(src[0] * pr) *
         cos(abs(dst[0]) * pr) *
         sin((src[1] - dst[1]) * pr / 2) ** 2
      )
   )

Convert bytes to int in python

Emulate:

void main(const void * key)
{
   const unsigned char * data = (const unsigned char *)key;
   unsigned int k = *(unsigned int *)data;
   while(len >= 4)
   {
      unsigned int k = *(unsigned int *)data;
      printf('%s\n', k);
   }
}

In Python:

key = 'abcdefg'
for i in range(0, len(key), 4):
   k = sum(ord(_c)<<(_i*8) for _i,_c in enumerate(reversed(key[i:i+4])))
   print k

Mortonize and reverse

Sources:

See it on ActiveState

B=(0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000ffff)

def mortonize(x, y):
   x = (x | (x << 8)) & B[3]
   x = (x | (x << 4)) & B[2]
   x = (x | (x << 2)) & B[1]
   x = (x | (x << 1)) & B[0]

   y = (y | (y << 8)) & B[3]
   y = (y | (y << 4)) & B[2]
   y = (y | (y << 2)) & B[1]
   y = (y | (y << 1)) & B[0]

   return x | (y << 1)

def unmorton(z, y=0):
   if y:
      z<<= 1
   v = z & B[0]
   v = (v ^ (v >> 1)) & B[1]
   v = (v ^ (v >> 2)) & B[2]
   v = (v ^ (v >> 4)) & B[3]
   v = (v ^ (v >> 8)) & B[4]
   return v

Chunk split

See http://php.net/chunk_split and http://stackoverflow.com/questions/959780/chunk-split-in-python

def chunk_split(body, chunklen=76, end='\r\n'):
  return end.join(
    body[i:min(i+chunklen, len(body))]
    for i in xrange(0, len(body), chunklen)
  )

Obtenir le multiple de deux supérieur à X

def powof(X):
   X-= 1
   X|= X >> 1
   X|= X >> 2
   X|= X >> 4
   X|= X >> 8
   X|= X >> 16
   return X+1

Valeur capee a un maximum

val = ((abs(val + max) - abs(val - max)) >> 1)