uc_authcode 函数的 Python 实现.

很多其他语言开发的网站程序需要整合到UCenter中，但是由于 UCenter 是使用
PHP开发的，很难移植。其中最难缠的 uc_authcode.
测试实现了 uc_authcode 函数。纯 python，无三方库。


This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#  FileName    : uc_authcode.py 
#  Author      : Feather.et.ELF  
#  Created     : Fri Mar 25 00:11:57 2011 by Feather.et.ELF 
#  Copyright   : Feather Workshop (c) 2011 
#  Description : uc_authcode in python 
#  Time-stamp: <2011-03-25 00:12:13 andelf> 


def uc_authcode(string, op='DECODE', key='', expiry=0):
    import time as t
    import base64
    import hashlib

    md5 = lambda s: hashlib.md5(s).hexdigest()
    microtime = lambda : str(t.time())
    time = lambda : int(t.time())

    ckey_length = 4

    key = md5(key) # or use key = md5(key or UC_KEY)
    keya = md5(key[:16])
    keyb = md5(key[16:])
    if op == 'DECODE':
        keyc = string[:ckey_length]
    else:
        keyc = md5(microtime())[-ckey_length:]

    cryptkey = keya + md5(keya + keyc)
    key_length = len(cryptkey)

    if op == 'DECODE':
        string = base64.b64decode(string[ckey_length:])
    else:
        string = ('%010d' % (expiry + time() if expiry else 0)) + \
                 md5(string + keyb)[:16] + string

    string_length = len(string)
    result = ''

    box = range(256)

    rndkey = [ord(cryptkey[i % key_length]) for i in xrange(256)]
    
    j = 0
    for i in xrange(256):
        j = (j + box[i] + rndkey[i]) % 256
        box[i], box[j] = box[j], box[i]

    a = j = 0
    for i in xrange(string_length):
        a = (a + 1) % 256
        j = (j + box[a]) % 256
        box[a], box[j] = box[j], box[a]
        result += chr(ord(string[i]) ^ (box[(box[a] + box[j]) % 256]))

    if op == 'DECODE':
        try:
            # use assert to catch misc case
            assert (int(result[:10])== 0) or (int(result[:10]) - time()> 0)
            if result[10:26] == md5(result[26:] + keyb)[:16]:
                return result[26:]
            else:
                return ''
        except:
            return ''
    else:
        return keyc + base64.b64encode(result).replace('=', '')

def test():
    APP_KEY = 'x2ta5X12oTz75gbRTMB6gY6thZ7D83'
    text = 'this_is_the_string_to_be_encrypted'
    print 'text=', text
    e = uc_authcode(text, "ENCODE", APP_KEY)
    print 'e=', e
    e += '='*(len(e) % 4)               # must fix padding
    assert uc_authcode(e, "DECODE", APP_KEY) == text
    
    print 'rslt=', uc_authcode(e, "DECODE", APP_KEY)


if __name__ == '__main__':
    test()

[IronPython]WPF应用的 STAThread 属性处理

最近用铁蟒写 WPF 应用, 遇到纠结的问题. (使用 tools/pyc.py 编译时会遇到, 解释执行正常) 任何一个 WPF 程序,Main 的前面都必须有 [STAThread] 属性, 否则会有运行时错误: Unhandled Exception: System.InvalidOperationException: The calling thread must be STA, because many UI components require this. 找了下相关资料 发现有 http://www.ironpython.info/index.php/Setting_the_Clipboard 整了个还算 Pythonic 的方法, 这里和大家分享下 from System.Threading import Thread, ParameterizedThreadStart, \ ApartmentState, ThreadStart def STAThread(main): def new_main(*args, **kwargs): t = Thread(ParameterizedThreadStart(main)) t.ApartmentState = ApartmentState.STA t.Start(*args, **kwargs) return new_main 这样, 可以直接使用 @STAThread 修饰主函数. 由于使用了 ParameterizedThreadStart, 主函数必须接受参数. 然后想到了版本2 def STAThread(main): if main.__code__.co_argcount: # if main accept params def new_main(*args, **kwargs): t = Thread(ParameterizedThreadStart(main)) t.ApartmentState = ApartmentState.STA t.Start(*args, **kwargs) else: def new_main(): t = Thread(ThreadStart(main)) t.ApartmentState = ApartmentState.STA t.Start() return new_main 需要注意的是, 如果主函数写在 class 里,那么 @STAThread 必须在 @staticmethod 之后, 原因..(如果你知道 @ 是什么意思的话). 或许有其他更好的方法, 欢迎讨论 :)

质数/素数 Haskell 求解

在 ProjectEuler 经常遇到质数求解的问题, 需要一个够强大的算法. 尝试自己写了个, 用了 Memoization:

primeList :: [Integer]
primeList
= 2:3:5:[p | p <- [7,9..]
      , all ((0 /=) . mod p) $ takeWhile (<= ceiling $ sqrt $ fromInteger p) primeList ]

在 Hugs 下测试:

Main> primeList !! 1000
7927 :: Integer
(3341273 reductions, 4756123 cells, 5 garbage collections)

貌似不错, 但是很明显, 代码适用范围有限, 例如 primeList !! 10000 在半天后终于出结果. ssword 提供了一个更短的算法, 目测貌似没我的效率高:

primes :: [Integer]
primes = sieve [2..]
    where sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]

代码相当巧妙, 很不错的筛选法, 但是效率实测... 估计是时间花在 [] 上和不断的回朔上, Lazy 嘛~ 发现用到下个值只好回朔到 2, 3, 5, 7, 11, 13....

Main> primes !! 1000
7927 :: Integer
(35111063 reductions, 51142767 cells, 59 garbage collections)

以上算法都只是处理小质数数列, 遇到大质数.... 全部死掉. PS, stack overflow. 熟悉的错误. 我找到了这个 http://en.wikipedia.org/wiki/Miller-Rabin_test, 感觉不错, 下面的 Haskell 算法是自己写的, 很丑陋.... 根据 Python 代码改的. Miller Rabin 筛选法.

-- Miller-Rabin methold By Andelf
-- true for p < 10^16 except `46 856 248 255 981’, so you can add 13
-- optimize: order of and, or, any, all/ all judge to odd/even
isPrime :: Integer -> Bool
isPrime p
    | p == 2          = True 
    | even p || p < 2 = False
    | otherwise    
        = all (isPrimeTest p) (takeWhile (< p) [2, 3, 7, 61, 24251])
    where 
      isPrimeTest :: Integer -> Integer -> Bool   
      isPrimeTest n a 
          = odd d || t == n - 1 
          where 
            (t, d) = loop (pow a (n-1) n) (shiftTillOdd (n - 1))
            loop t d = if t /= 1 && d /= n - 1 && t /= n - 1 
                       then loop (t * t `mod` n) (d + d) 
                       else (t, d)
            shiftTillOdd = until odd $ flip div 2
            pow :: Integer -> Integer -> Integer -> Integer 
            pow a d n
                | even d            = pow (a * a `mod` n) (d `div` 2) n `mod` n 
                | d == 1 || a == 1  = a
                | otherwise         = pow (a * a `mod` n) (d `div` 2) n * a `mod` n

本来想用 AKS 的, 后来发现在多项式判断那块时间太长, 所以还是采用了伪素数算法, 你所看到的第 2 行注释, p < 10^16 except `46 856 248 255 981’ 是没问题的. 代码经过简单优化, guard 判断的分支顺序可能很诡异, mod, even, odd, 等函数的使用可能也很诡异, 但请相信这个是在 Hugs 下测试过的, 目前是最优. div/(+) 就是比 Data.Bits 快很多. 很诡异. ghc 同学请自己权衡. 再次动手可能在 pow 函数上. [2, 3, 7, 61, 24251] 的选择请参考链接.

Main> head $ filter isPrime [10 ^ 100..]
100000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000267 :: Integer
(8965148 reductions, 25399307 cells, 29 garbage collections)

参考链接

• http://en.wikipedia.org/wiki/Miller-Rabin_test
• http://en.literateprograms.org/Miller-Rabin_primality_test_(Python) 很多语言的实现
• http://primes.utm.edu/prove/prove2_3.html

不是最优, 仅供参考.

python 的 yield

以前只是类似生成器表达式那样使用... 其实有N多牛B用法. 真长见识~! http://www.dabeaz.com/coroutines/index.html 例如:

# grep.py
#
# A very simple coroutine

def grep(pattern):
  print "Looking for %s" % pattern
  while True:
    line = (yield)
    if pattern in line:
         print line,
# Example use
if __name__ == '__main__':
  g = grep("python")
  g.next()
  g.send("Yeah, but no, but yeah, but no")
  g.send("A series of tubes")
  g.send("python generators rock!")

对于生成器函数来说, 有 next() ,send(), throw() 方法.

• next() 比较容易理解.
• send(arg) 向生成器发送参数, 会被 line = (yield) 捕获.
• throw(typ[,val[,tb]]) -> raise exception in generator, return next yielded value or raise StopIteration. 参数分别是, 异常类型, 异常 str, traceback object.

这算是最简单的.... 配合函数修饰符, 相当强大.... yield ...

数据结构=brainfucking.作业.

设计一个算法,用尽可能少的辅助空间将顺序表前 m 个元素和后 n 个元素进行互换. {a1,a2,a3..am,b1,b2,b3..bn} => {b1,b2,b3..bn,a1,a2,a3..am} 让我想起某单词. brainfucking. now let's fucking. 问题简化到 int 数组吧. 差不多. 函数原型:

void swapSeq(int *lst, int m, int n);

惯例, lst 索引为 1..(m n) "用尽可能少的辅助空间"..... 果然 brainfucking. 函数里定义某数组, 把 b1~bn, a1~am 按顺序复制再拿出来, OK. 不好玩. 直觉告诉我们, 既然是 brainfucking..... Show 实现.

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         tmp = lst[i];
         lst[i] = lst[m i];
         lst[m i] = tmp;
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

发现可爱的尾递归. OK, 立即抛弃, 上 while~!

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             tmp = lst[i];
             lst[i] = lst[m i];
             lst[m i] = tmp;
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}

---

抛弃题目本质. BT 下. BT 无罪.

void swapSeq(int *lst, int m, int n)
{
   int i;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         lst[i]^= lst[m i];
         lst[m i]^= lst[i];
         lst[i]^= lst[m i];
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

其实递归未优化的消耗还是很大的, 开优化另说.

void swapSeq(int *lst, int m, int n)
{
   int i;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             lst[i]^= lst[m i];
             lst[m i]^= lst[i];
             lst[i]^= lst[m i];
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}

字符计数

Smalltalk(8063446)  8:58:35 
>>> from collections import Counter 
>>> c=Counter() 
>>> for letter in 'here is a sample of english text':
...   c[letter] += 1 
... 
>>> c
Counter({' ': 6, 'e': 5, 's': 3, 'a': 2, 'i': 2, 'h': 2, 'l': 2, 't': 2, 'g': 1, 'f': 1, 'm': 1, 'o': 1, 'n': 1, 'p': 1, 'r': 1, 'x': 1}) >>> c['e'] 5 >>> c['z'] 0 
;; 其实是个 reduce 过程.  
Feather(85660100)  11:45:28 
>>> reduce(lambda d,s: dict(d, **{s:d.get(s,0)+1}), \
            'here is a sample of english text', {}) 
{'a': 2, ' ': 6, 'e': 5, 'g': 1, 'f': 1, 'i': 2, 'h': 2, 'm': 1, 'l': 2, 'o': 1, 'n': 1, 'p': 1, 's': 3, 'r': 1, 't': 2, 'x': 1} 

其实要说的是.... dict() 很强大很强大. 以及其他 python type 函数.

百度谷歌造[有图有真相][baidu made from google]

有图有真相... 上图:

---

真相:

#!win32 only. no unix magic chars
# coding=utf-8

# need pywin32 module
import win32com.client

bro = win32com.client.Dispatch("InternetExplorer.Application")
# show window
bro.Visible = True
bro.Navigate("http://www.baidu.com")

while bro.Busy:
    pass

print bro.LocationName
# MSDN: bro.Document is a DOM object
doc = bro.Document
logo = doc.getElementsByTagName('img')[0]
logo.setAttribute('src', 'http://www.google.cn/intl/zh-CN/images/logo_cn.gif')
logo.setAttribute('width', '286')
logo.setAttribute('height', '110')

HTTP Basic 验证HTTPBasicAuthHandler

以 fanfou api 为例说明. 有兴趣的可以做个功能完整的工具.

#!/usr/bin/python
# coding=utf-8

import urllib2
import xml.dom.minidom
import winsound
import time
import thread
import urllib

public_timeline_url = "http://api.fanfou.com/statuses/public_timeline.xml"
user_timeline_url = "http://api.fanfou.com/statuses/user_timeline.xml"
friends_timeline_url = "http://api.fanfou.com/statuses/friends_timeline.xml"
statuses_update_url = "http://api.fanfou.com/statuses/update.xml"


# friendship related
friendships_create_url = "http://api.fanfou.com/friendships/create.xml"
friendships_destroy_url = "http://api.fanfou.com/friendships/destroy.xml"

# block list
blocks_create_url = "http://api.fanfou.com/blocks/create.xml"
blocks_destroy_url = "http://api.fanfou.com/blocks/destroy.xml"

passwd_mgr = urllib2.HTTPPasswordMgrWithDefaultRealm()
passwd_mgr.add_password(realm=None,
                          uri='http://api.fanfou.com/',
                          user='xxxxxxx',
                          passwd='xxxxxxxxx') # 用户名和密码

auth_handler = urllib2.HTTPBasicAuthHandler(passwd_mgr)
opener = urllib2.build_opener(auth_handler)

last_id = ''


def parseDom(doc):
    sts = doc.getElementsByTagName('status')
    get_textValue = lambda tag: \
        (lambda d:d.getElementsByTagName(tag)[0].childNodes[0].data)
    create_time = get_textValue('created_at')
    id_str = get_textValue('id')
    text = get_textValue('text')
    username = get_textValue('name')
    return [(username(node), text(node), create_time(node), id_str(node))
                for node in sts][::-1]

def refresh():
    global last_id
    print last_id
    res = opener.open(friends_timeline_url)
    doc = xml.dom.minidom.parseString(res.read())
    posts = parseDom(doc)
    id_list = [ids for (_, _, _, ids) in posts]
    if last_id in id_list:
        id_list = id_list[id_list.index(last_id)+1:]
        winsound.MessageBeep(winsound.MB_ICONASTERISK)
    print 
    for (user, txt, tm, ids) in posts:
        print "{%s}: %s [%s]" % (user, txt, tm.split()[3])
    last_id = posts[-1][-1]
    print 'MyMsg:',

def refresh_thread(times=0, timeout=60):
    f = False
    if times== 0:
        f = True
    while f or times:
        refresh()
        time.sleep(timeout)
    
def post_statue(msg, reply=''):
    if not msg:
        return
    #msg = unicode(msg, 'gbk')
    data = {'status' : msg,
            'in_reply_to_status_id' : reply,
            'source' : 'ffsh'}
    data = urllib.urlencode(data)
    opener.open(statuses_update_url, data)
  

thread.start_new_thread(refresh_thread, (0,30))

while True:
    mymsg = raw_input('MyMsg: ')
    post_statue( mymsg ) 
    

用 python 暴百度贴吧

当然, 只是原型, 但基本功能有了. 目前在刷回帖的时候会有乱码, 编码问题需要解决. 成果展示: ---------------------------------------------------------------

#!/usr/bin/python
# -*- coding:utf-8 -*-

import urllib2
import urllib
import socket
import libxml2dom
import Image
import time



def domToQueryDict(doc, formIndex=0):
   data = {}
   form = doc.getElementsByTagName('form')[formIndex]
   nodes = form.getElementsByTagName('input')
   nodes.extend(form.getElementsByTagName('textarea'))
   for node in nodes:
       if node.hasAttribute('name') and node.getAttribute('type')!= u"submit":
           if node.hasAttribute('value'):
               data[node.getAttribute('name')] = \
                   node.getAttribute('value').encode('gbk', 'ignore')
           else:
               data[node.getAttribute('name')] = ""
   return data

             
cookie_handler = urllib2.HTTPCookieProcessor()
opener = urllib2.build_opener(cookie_handler)
urllib2.install_opener(opener)

# 获得登陆数据
url = "http://passport.baidu.com/?" + \
   "login&tpl=tb&u=http%3A//tieba.baidu.com/f%3Fkw%3Dpython"
doc = libxml2dom.parseString(opener.open(url).read(), html=1,
                            htmlencoding='gbk')
data = domToQueryDict(doc)

# 用户名/密码设置
data[u'username'] = '用户名'
data[u'password'] = '密码'

# 验证图片处理
veryfyPic = opener.open("https://passport.baidu.com/?verifypic")
picfile = file("pic.jpg", 'wb')
picfile.write(veryfyPic.read())
picfile.close()
im = Image.open("pic.jpg")
im.show()
data["verifycode"] = raw_input("What you see?").strip()

# 登陆页面
data = urllib.urlencode(data)
b = opener.open(url, data)  # here login OK
print b.read()
print '-'*20

for i in xrange(20):
   # 分析主页数据
   # url = "http://tieba.baidu.com/f?kz=543530949"
   b = opener.open("http://tieba.baidu.com/f?kw=python&t=1")
   frontpage = b.read()
   doc = libxml2dom.parseString(frontpage, html=1, htmlencoding='gbk')
             
   data = domToQueryDict(doc, 1)
   print "*",
   # 发贴标题及内容
   data[u'ti'] = "Fledna 自爆专用~!!!!!!!!!!!!!!"+str(i)
   data[u'co'] = "For Test only. " + str(i)
   print data[u'ti']
   data = urllib.urlencode(data)
   post_url = "http://tieba.baidu.com/f"
   b = opener.open(post_url, data)
   time.sleep(20)