rp.py

# -*- coding: UTF-8 -*-

from contextlib import contextmanager
import random

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_letters = ascii_lowercase + ascii_uppercase + ' '

radixPrime = 3

max_short_string_len = 1 << 5

def rolling_hash(x):
    h = 0
    for c in x:
        h = h * radixPrime + ord(c)
    return h, pow(radixPrime, len(x))

def index_char(string, char):
    assert len(char) == 1
    for i, x in enumerate(string):
        if x == char:
            return i
    return -1

def index_short_string(string, sep):
    for i in range(len(string) - len(sep) + 1):
        if string[i:i+len(sep)] == sep:
            return i

    return -1

def index_rp(string, sep):
    n = len(sep)
    if n == 0:
        return 0

    if len(string) < n:
        return -1

    if n == 1:
        return index_char(string, sep)

    if len(string) == n:
        if string == sep:
            return 0
        return -1

    if len(string) < max_short_string_len:
        return index_short_string(string, sep)

    h, p = rolling_hash(sep)
    u = 0
    for i in range(n):
        u = u * radixPrime + ord(string[i])

    if u == h and string[:n] == sep:
        return 0

    i = n
    while i < len(string):
        u = u * radixPrime + ord(string[i])
        u -= ord(string[i - n]) * p
        i += 1
        if u == h and string[i-n:i] == sep:
            return i - n

    return -1

def get_addresses(src):
    MAIL_BEGIN = 'mailto:'
    MAIL_END = '"'

    addresses = []

    while src:
        i = index_rp(src, MAIL_BEGIN)
        if not ~i:
            break

        src = src[i + len(MAIL_BEGIN):]
        j = index_rp(src, MAIL_END)
        if not ~j:
            break

        address = src[:j]
        src = src[j:]

        addresses.append(address)

    return addresses


VigenereTableau = [
 [' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'],
 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' '],
 ['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a'],
 ['c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b'],
 ['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c'],
 ['e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd'],
 ['f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e'],
 ['g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f'],
 ['h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g'],
 ['i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'],
 ['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'],
 ['k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
 ['l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'],
 ['m', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'],
 ['n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm'],
 ['o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n'],
 ['p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o'],
 ['q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'],
 ['r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q'],
 ['s', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r'],
 ['t', 'u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's'],
 ['u', 'v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't'],
 ['v', 'w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u'],
 ['w', 'x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v'],
 ['x', 'y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w'],
 ['y', 'z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x'],
 ['z', ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'],
]

ord_a = ord('a')
# ord_z = ord('z')

def numbered(char):
    if char == ' ':
        return 0

    char = char.lower()
    return ord(char) - ord_a + 1

def vigenere_encrypt(raw, keywords):
    # itertools.cycle
    pos = 0
    buf = ''

    for char in raw:
        keyword = keywords[pos % len(keywords)]
        keyword = numbered(keyword)
        pos += 1
        buf += VigenereTableau[keyword][numbered(char)]

    return buf

# 첫 번째 문제 해답
def P1():
    a = vigenere_encrypt('attack safe zone', 'abc')
    b = 'bvwbenaudggc qqf'
    print(a)
    print(b)
    print(a == b)

# 추가 과제
def P1_2():
    print(vigenere_encrypt('attack safe zone', 'abcdefghijk'))
    print(vigenere_encrypt('attack boring zone', 'tpwhdeodhkd'))
    print(vigenere_encrypt('modular multiplicative inverse', 'solving congruence'))

# 두 번째 문제 해답
def P2():
    # Py_DECREF 가 refcount 를 0 으로 만들꺼니까 FD Leak 을 못잡아내진 않는다.
    # ResourceWarning 은 무시하자
    src = open('source', encoding='utf-8').read()
    addresses = get_addresses(src)

    for address in addresses:
        print(address)

class Failure(Exception):
    def __init__(self, name, args, expected, ret):
        super().__init__()
        self.name = name
        self.args = args
        self.expected = expected
        self.ret = ret

    def __str__(self):
        return "{}{} expected {} but returned {}".format(
            self.name, self.args, self.expected, self.ret)

def doTDT(fn, cases):
    for args, expected in cases:
        ret = fn(*args)
        if ret != expected:
            raise Failure(fn.__name__, args, expected, ret)

def do_comparison(fn, proven, inargs):
    # kwd 귀찮음
    for args in inargs:
        expected = proven(*args)
        ret = fn(*args)
        if expected != ret:
            raise Failure(fn.__name__, args, expected, ret)

@contextmanager
def activate_verifier():
    try:
        yield
    except Failure as fail:
        print(fail)

def create_alpha_text(n):
    arr = bytearray(n)
    for i in range(n):
        arr[i] = ord(random.choice(ascii_letters))
    return arr.decode()

def verify_index_fn():
    index_char_table = [
        (('abcdefg', 'f'), 5),
        (('abcdefg', 'b'), 1),
        (('abcdefg', 'a'), 0),
        (('abcdefg', 'h'), -1),
    ]

    index_short_string_table = [
        (('abcdefg', 'def'), 3),
        (('abcdefg', 'abc'), 0),
        (('abcdefg', 'abg'), -1),
    ]

    index_rp_table = [
        (('abcde', 'cde'), 2),
        (('19232', '233'), -1),
        (('2982',  '82'), 2),
        (('01231654658976564654654654132134657468787974',  '7974'), 40),
        (('01231654658976564654654654132134657468787974',  '10100000'), -1),

    ]
    index_rp_table.extend(index_char_table)
    index_rp_table.extend(index_short_string_table)

    doTDT(index_char, index_char_table)
    doTDT(index_short_string, index_short_string_table)
    doTDT(index_rp, index_rp_table)

    def supplier():
        for i in range(100):
            n = random.randint(0, 100)
            m = random.randint(0, n)
            yield (create_alpha_text(n), create_alpha_text(m))

    def proven_index_fn(s, sep):
        return s.find(sep)

    do_comparison(index_rp, proven_index_fn, supplier())

def main():
    DO_VERIFICATION = False
    if DO_VERIFICATION:
        with activate_verifier():
            verify_index_fn()

if __name__ == '__main__':
    main()