UOJ自动配置题目数据

计划未来几个星期进行线上测试,所以最近就挑了 UOJ (https://github.com/UniversalOJ/UOJ-System )来部署。用 Docker 倒是简单,就是题目数据有些难。虽然之前在其他 OJ 上有过数据和代码,但要逐个导入也是麻烦。目前的方法大概是这样的:1)通过 Docker 的配置把 UOJ 的题库数据目录 (/opt/uoj_data ) 外挂到主机目录;2)执行下面的脚本,根据标程和 input,自动生成 output 和配置problem.conf

注:由于我是在 WSL2 通过网络驱动器(SMB)的形式访问题库数据目录。居然默认不支持,需要执行下面的命令手动挂载 WSL2 主机的网络驱动器。

sudo mkdir /mnt/y
sudo mount -t drvfs Y: /mnt/y

下面的是Linux下的Bash脚本代码:

#!/bin/bash

cur_pwd=$PWD

input_name=input
output_name=output
ext_name=txt
problem_conf=problem.conf
uoj_data_dir=/mnt/y/opt-uoj.tpu01yzx.me/uoj_data/upload/

echo "UOJ_DATA_DIR: $uoj_data_dir"

#sudo mkdir /mnt/y
#sudo mount -t drvfs Y: /mnt/y

i=0
while [ true ]; do
  i=$(($i + 1));
  if [ ! -d "$uoj_data_dir/$i" ]; then
	break;
  fi;
done;
problem_id=$(($i - 1));

echo "Found Problem ID: $problem_id"

(
cd $uoj_data_dir/$problem_id ;
std_src=$(ls std*.cpp | head -n 1) 
if [ ! -e $std_src ]; then
	echo "No Standard Source File was Found."
	exit;
fi;
exe_name=main_$problem_id
gcc $std_src -Wall -o $exe_name
if [ ! -e "$exe_name" ]; then
	echo "Compile Standard Source Failed."
	exit;
fi;
for p in "ex_"  "" ; do
	echo "p: $p"
	i=0
	while [ true ]; do
	  i=$(($i + 1));
	  input_file=${p}${input_name}${i}.${ext_name}
	  if [ ! -e "$input_file" ]; then
		break;
	  fi;
	  echo "$input_file is found."
	  output_file=${p}${output_name}${i}.${ext_name}
	  ./$exe_name < "$input_file" > "$output_file"
	  if [ ! -e "$output_file" ]; then
		echo "$output_file is NOT generated. "
	  else
		echo "$output_file is generated. "
	  fi;	  
	done;
	i=$(($i - 1));
	echo "Total $i tests."
	conf_key="n_${p}tests"
	sed -E 's/'"${conf_key}"'[[:blank:]]+[[:digit:]]+/'"${conf_key} ${i}"'/' $problem_conf > ${problem_conf}.new
	rm -f $problem_conf
	mv ${problem_conf}.new $problem_conf
done;
rm -f $exe_name
cat $problem_conf
)

AKS素性检测算法的C语言实现

按道理说这个算法提出之后,应该是有很多语言的实现版本。但是对于多项式的方幂运算,C语言版本总感觉缺少点什么。以前在其他地方见过,但多项式方幂的实现算法复杂度较高。因此自己也实现一个版本。但目前遇到一个问题,就是64bit的两个整数相乘,会溢出。虽然是在模n(也是64bit的)下运算的,但为了避免溢出,好好的乘法非要改用加法实现。希望在这方面可以有改进的地方( Mul64Mod )。

备注:2022年11月1日修订。根据文献[3]的提示,GNU G++17可以使用 unsigned __int128 数据类型,虽然我的编译器( g++.exe (MinGW-W64 x86_64-ucrt-posix-seh, built by Brecht Sanders) 12.2.0 )提示使用的数据类型应该为 __uint128_t 。但起码目前模乘法的速度问题算是基本解决了。另外,我将当前版本保存了一份在网上:https://onlinegdb.com/dFtGoQgL6 或者 https://gist.github.com/tpu01yzx/172c65d3003bb3a09a941e69bc6c370b

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <memory.h>
#include <math.h>

#define N 100
#define MAX_FACTORS 32
#define MAXR 320

typedef unsigned long long int uint64;
typedef unsigned int uint32;
typedef unsigned char uint8;

uint64 gcd(uint64 a, uint64 b) {
    uint64 c = a;
    while(b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

uint8 BitCount(uint64 n) {
    uint8 ans = 0;
    while(n) {
        n>>=1;
        ans++;
    }
    return ans;
}

uint32 SquareRoot(uint64 x) {
    if(x < (1ULL<<32)) {
        return (uint32)sqrt((uint32)x);
    }
    uint8 logx = BitCount(x);    
    uint32 l = pow(2.0, (double)(logx-1) / 2);
    uint32 r = pow(2.0, (double)(logx) / 2);
    uint32 m = l;
    uint64 m2 = x;

    while(l <= r) {        
        m = (l + r ) / 2;        
        m2 = m * m;
        
        if(m2 == x) return m;
        if(m2 < x) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return m;
}

uint64 Power(uint32 a, uint8 k) {
    if(k == 0) return 1;

    uint64 ans = 1;
    uint64 a2 = a;
    while(k > 1) {
        if(k & 0x01) {
            ans *= a2;
        }
        a2 = a2 * a2;
        k>>=1;
    }
    ans *= a2;
    return ans;
}

uint32 PowerMod(uint32 a, uint8 k, uint32 mod) {
    if(k == 0) return 1;

    uint64 ans = 1;
    uint64 a2 = a % mod;    
    while(k > 1) {
        if(k & 0x01) {
            ans = (ans * a2) % mod;            
        }
        a2 = (a2 * a2) % mod;        
        k>>=1;
    }
    ans = (ans * a2) % mod; 
    return (uint32)ans;
}

uint64 Mul64Mod(uint64 a, uint64 b, uint64 mod) {
    return (__uint128_t)a * b % mod;
}

void MulPoly(uint64 *p1, uint64 *p2, uint64 n, uint32 r) {
    uint64 ans[MAXR];
    int i, j;

    memset(ans, 0, sizeof(uint64) * r);
    for(i = 0; i < r; i++) {
        for(j = 0; j <= i; j++) {
            ans[i] += Mul64Mod(p1[j], p2[i - j], n);
            if(ans[i] >= n) ans[i] -= n;
        }
        for(j = i + 1; j < r; j++) {
            ans[i] += Mul64Mod(p1[j], p2[r + i - j], n);
            if(ans[i] >= n) ans[i] -= n;
        }        
    }    
    memcpy(p1, ans, sizeof(uint64) * r);
}

void PowerPoly(uint64 *coff, uint64 n, uint32 r) {
    if(n == 0) {
        memset(coff, 0, sizeof(uint64) * r);
        coff[0] = 1ULL;
        return;
    }
    uint64 n0 = n;
    uint64 ans[MAXR];
    uint64 coff2[MAXR];
    memset(ans, 0, sizeof(uint64) * r);    ans[0] = 1ULL; 
    memcpy(coff2, coff, sizeof(uint64) * r);

    while(n > 1) {
        if(n & 0x01) {
            MulPoly(ans, coff2, n0, r);
        }
        MulPoly(coff2, coff2, n0, r);
        n>>=1;
    }
    MulPoly(ans, coff2, n0, r);
    
    memcpy(coff, ans, sizeof(uint64) * r);
}

int CheckPoly(uint64 *p, uint64 a, uint64 n, uint32 r) {
    uint64 n0 = n % r;
    uint32 i;
    if(p[0] != a) return 0;    
    for(i = 1; i < n0; i++) {
        if(p[i] != 0) return 0;
    }
    if(p[n0] != 1ULL) return 0;
    for(i = n0 + 1; i < r; i++) {
        if(p[i] != 0) return 0;
    }
    return 1;
}

uint32 PerfectRoot(uint8 a, uint64 n, uint8 logn) {    
    if(a == 1) return n;
    uint32 l = pow(2.0, (double)(logn-1) / a);;
    uint32 r = pow(2.0, ((double)(logn) / a));
    uint32 m;
    uint64 mp;
    while(l <= r) {
        m = (l + r) / 2;
        mp = Power(m, a);
        if(mp == n) return m;
        if(mp < n) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return 0;
}

int IsPower(uint64 n) {
    uint8 i, j;
    uint8 cnt = BitCount(n);
    for(i = 2; i < cnt; i++) {
        if(PerfectRoot(i, n, cnt)) return 1;
    }
    return 0;
}

uint8 SmallFactors(uint32 r, uint32 *factors, uint32 *exponents) {
  uint32 i;
  uint32 sqrtr = SquareRoot(r);
  uint8 p = 0;
  for(i = 2; i <= sqrtr; i++) {
      if(r % i == 0) {
          factors[p] = i;
          exponents[p] = 0;
          while(r % i == 0) {
              r /= i;
              exponents[p]++;
          }
          p++;
          sqrtr = SquareRoot(r);
      }
  }
  if(r > 1) {
      factors[p] = r;
      exponents[p] = 1;
      p++;
  }
  return p;
}

uint32 SmallOrder(uint32 n, uint32 r) {
  uint32 i;
  uint32 factors[MAX_FACTORS];
  uint32 exponents[MAX_FACTORS];
  uint32 p;    
  uint32 ans;
  
  ans = 1;
  p = SmallFactors(r, factors, exponents);
  for(i = 0; i < p; i++) {
    if(exponents[i] > 1) {
      ans *= Power(factors[i], exponents[i] - 1);    
    }
    ans *= factors[i] - 1;
  }
  
  p = SmallFactors(ans, factors, exponents);
  for(i = 0; i < p; i++) {
    while(ans % factors[i] == 0) {
      if(PowerMod(n, ans, r) == 1) {
        ans /= factors[i];
      } else {
        break;
      }
    }
    if(ans % factors[i] == 0) {
      ans *= factors[i];
    }
  }
  return ans;
}


uint32 FindR(uint64 n) {
    uint32 r, k;    
    uint8 logn = BitCount(n);
    uint32 maxr = Power(logn, 5);
    uint32 maxk = Power(logn, 2);
    if(maxr < 3) maxr = 3;    
    for(r = 2; r <= maxr; r++) {
        if(gcd(n, r) > 1) continue;   
        k = SmallOrder(n % r, r);
        if(k > maxk) break;
    }
    return r;
}


uint32 SmallPhi(uint32 r) {
    uint32 ans;
    uint32 i;    
    uint32 factors[MAX_FACTORS];
    uint32 exponents[MAX_FACTORS];
    uint32 p;    
    p = SmallFactors(r, factors, exponents);
    ans = 1;
    for(i = 0; i < p; i++) {
        if(exponents[i] > 1) {
          ans *= Power(factors[i], exponents[i] - 1);    
        }
        ans *= factors[i] - 1;
    }
    return ans;
}

int IsPrimeAKS(uint64 n) {
    uint64 i = 0;
    uint32 r = 0;
    uint64 t = 0;
    uint32 logn = 0;
    uint64 maxa = 0;
    uint64 poly[MAXR];

    if(IsPower(n)) return 0;    

    r = FindR(n);

    for(i = 2; i <= r; i++) {
        t = gcd(n, i);
        if(t > 1 && t < n) return 0;
    }

    if(n <= r) return 1;

    logn = BitCount(n);
    maxa = ((uint64)logn) * SquareRoot(SmallPhi(r));
    if(maxa >= n) maxa = n - 1;


    for(i = 1; i <= maxa; i++) {      
        memset(poly, 0, sizeof(uint64) * r);
        poly[0] = i; poly[1] = 1;                
        PowerPoly(poly, n, r);
        if(!CheckPoly(poly, i, n, r)) return 0;
    }

    return 1;
}


int main()
{  
    uint64 n;
    while(scanf("%"SCNu64, &n) != EOF) {
        printf("%s\n", IsPrimeAKS(n) ? "Yes" : "No");
    }
    return 0;
}


参考文献:

MathType和Office整合的方法

本文主要讨论的是MathType和Office正常使用之后,由于某些其他原因导致两者之间的集成出现各种问题的应对方法。

MathType的版本建议采用6.9b,高于这个版本的似乎不支持Office 2003,低于这个版本的似乎不支持Office 2016。而我的电脑上恰好都安装了Office 2003和Office 2016,所以只能选择MathType 6.9b这个版本。

零、相关约定
为了描述方便,对几个常用的文件夹做个变量:

  • MT_HOME表示MathType的安装路径,例如我的电脑上是 E:\Green\MathType
  • O2003_PG_DIR表示Office 2003的主目录(不是安装目录),例如我的电脑上是 C:\Program Files (x86)\Microsoft Office\OFFICE11\
  • O2016_PG_DIR表示Office 2016的主目录(不是安装目录),例如我的电脑上是 C:\Program Files (x86)\Microsoft Office\OFFICE16\
  • O_USER_DIR表示用户目录下的Office配置目录,例如我的电脑上是 C:\Users\{UserName}\AppData\Roaming\Microsoft\Word\ , 其中 {UserName} 表示的是当前系统的登陆用户名。
  • OBITS表示Office的版本,这里特指32位或者64位。

一、MathPage的整合
MathType.wll其实是dll文件,可以被Office加载,这个文件位于 $MT_HOME\MathPage\$OBITS\MathPage.wll 。主要用于Office界面中插入显示MathType的工具界面。
对于Office 2003,把这个文件复制到 $O2003_PG_DIR ;对于Office 2016,似乎并不需要。

二、MathType Commands的整合
MathType Commands文件其实是Word的宏文件。对于Office 2003来说,文件名为 MathType Commands 6 For Word.dot (似乎不在安装目录中,我是从其他地方复制过来的,在文章的附件里有打包。),对于Office 2016来说,这个文件在 $MT_HOME\Office Support\$OBITS\MathType Commands 6 For Word 2016.dotm 。整合的时候,复制到 $O_USER_DIR\STARTUP

三、后续
经过一段时间使用后,为了方便,Office 2016也安装了32位的版本(Office 2003只有32位的版本),这就导致Office 2016会加载到为Office 2013准备的MathType Commands文件,从而引起冲突。具体的症状就是无法使用Ctrl+C和Ctrl+V复制粘帖功能。解决办法是,把 $MT_HOME\MathPage\$OBITS\MathPage.wll 也复制一份到$O2016_PG_DIR , 用来代替之前为Office 2016准备的MathType Commands文件(如果有,则删除 $O_USER_DIR\STARTUP\MathType Commands 6 For Word 2016.dotm )。

注:如果复制到其他加载目录中,可能会出现各种警告,但也不影响使用。本文附带一个附件以备不时之需:MathType和Office整合的所需文件打包

两种纯文本终端行下”录屏”的方法

方法一: script & scriptreplay
https://aws.amazon.com/cn/premiumsupport/knowledge-center/record-linux-terminal-or-ssh-session/
记录开始: script -a -t timingfile.txt typescript.txt
记录结束: exit
记录重放: scriptreplay --timing=timingfile.txt typescript.txt

方法二: ttyrec & ttyrec2video
https://github.com/jwodder/ttyrec2video
安装: sudo apt-get install ttyrec ffmpeg python3-pip
记录开始: ttyrec record.log
记录结束: exit
记录重放: ttyplay record.log

记录转视频需要用到 ttyrec2video
安装: sudo python3 -m pip install git+https://github.com/jwodder/ttyrec2video.git
修复Bug: sudo pip3 install imageio==2.4.1
转换: ttyrec2video record.log record.mp4

注:pip默认的源在国外很慢, 可以设置使用清华大学的源
sudo pip3 config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple

继续教育自动刷视频的脚本

这个脚本需要使用Firefox浏览器,安装TamperMonkey插件,然后在插件中安装如下脚本(或者从这个URL下载:https://raw.githubusercontent.com/tpu01yzx/AutoPlayVideo_jsglpt/main/AutoPlayVideo_jsglpt.js )。注意:自动播放视频可能会被Firefox禁止,请在地址栏的左边小图标中启用自动播放视频权限。

继续教育里的这个人工智能的课讲得一般,反正我是有认真看完的啦。这个脚本主要做了三件事情:
1)禁用看视频中途出现的回答问题动作,实现不间断播放视频。
2)定时刷新播放器状态,实现自动播放。
3)定时检测看视频状态,如果已经完成,则自动转到下一个视频的页面。
// ==UserScript==
// @name         继续教育自动刷视频
// @namespace    http://tampermonkey.net/
// @version      0.2
// @description  auto play videos!
// @author       tpu01yzx
// @match        https://jsglpt.gdedu.gov.cn/ncts/*
// @icon         https://www.google.com/s2/favicons?domain=gdedu.gov.cn
// @grant        none
// ==/UserScript==

(function() {
    'use strict';

    //var ajaxHook = function() {
    //    var $ = $ || window.$;
    //    $.ajaxSetup({beforeSend: function(xhr, settings) {
    //        //fix a error in updateLastViewTime for the old version.
    //        settings.url = settings.url.replace("/nctsa_", "/ncts/a_");
    //    }});
    //};
    //setTimeout(ajaxHook,1000);

    var main_func = function() {
        var $ = $ || window.$;

        var times = $('input[id^="time_"]');
        if(times && times.length > 0) {
            times.each(function(){ this.remove(); });
        }

        var player = player || window.player;
        var isComplete = isComplete || window.isComplete;

        if(isComplete && $('a[class="btn next crt"]')) {
            $('a[class="btn next crt"]').click();
        }
        if(player && player.V && player.loaded && !player.V.ended) {
            if(player.V.paused) player.videoPlay();
        }
        setTimeout(main_func, 1000);
    }
    if(window.player) setTimeout(main_func,1000);

    // Your code here...
})();

那个充满激情的岁月

那些年,我们一些为了BBS(网上论坛)而疯狂。为此,曾经刷在线时间(类似QQ刷太阳等级),动手在服务器上写了一个程序。作为留念,现决定低调开源。

#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <time.h>

#include <sys/stat.h>
#include <signal.h>
#include <unistd.h>
#include <fcntl.h>
#include <getopt.h>
//#include <iconv.h>

#define LOCKFILE "/var/run/bbs4gzhu.pid"

#define LOCKMODE (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)


int                 lockfile;                  /* 锁文件的描述字 */
int 		    exit_flag = 0;


#define BUFFER_SIZE	409600
#define FORMHASH_SIZE	16
#define USERNAME_SIZE	128
#define PASSWORD_SIZE	128
#define SID_SIZE	64
#define AUTH_SIZE	128

int		    background = 0;
int 		    interval = 15;
char 		   *cookiepath = "";
char 		   username[USERNAME_SIZE] = "";
char 		   password[PASSWORD_SIZE] = "";
char		   *host = "bbs.gzhu.edu.cn";
short 		   port = 80;


static void
flock_reg ()
{
    char buf[16];
    struct flock fl;
    fl.l_start = 0;
    fl.l_whence = SEEK_SET;
    fl.l_len = 0;
    fl.l_type = F_WRLCK;
    fl.l_pid = getpid();
 
    //阻塞式的加锁
    if (fcntl (lockfile, F_SETLKW, &fl) < 0){
        perror ("fcntl_reg");
        exit(EXIT_FAILURE);
    }
 
    //把pid写入锁文件
    ftruncate (lockfile, 0);    
    sprintf (buf, "%ld", (long)getpid());
    write (lockfile, buf, strlen(buf) + 1);
}

void
daemon_init(void)
{
	pid_t	pid;
    	int     fd0;

	if ( (pid = fork()) < 0)
	    perror ("Fork");
	else if (pid != 0) {
        	fprintf(stdout, "bbs4gzhu&&Info: Forked background with PID: [%d]\n\n", pid);
		exit(EXIT_SUCCESS);
    	}
	setsid();	/* become session leader */
	chdir("/tmp");		/* change working directory */
	umask(0);		/* clear our file mode creation mask */
    flock_reg ();

    fd0 = open ("/dev/null", O_RDWR);
    dup2 (fd0, STDIN_FILENO);
    dup2 (fd0, STDERR_FILENO);
    dup2 (fd0, STDOUT_FILENO);
    close (fd0);
}


static int 
is_running()
{
    struct flock fl;
    fl.l_start = 0;
    fl.l_whence = SEEK_SET;
    fl.l_len = 0;
    fl.l_type = F_WRLCK;
 
    //尝试获得文件锁
    if (fcntl (lockfile, F_GETLK, &fl) < 0){
        perror ("fcntl_get");
        exit(EXIT_FAILURE);
    }

    if (exit_flag) {
        if (fl.l_type != F_UNLCK) {
            if ( kill (fl.l_pid, SIGINT) == -1 )
            perror("kill");
            fprintf (stdout, "bbs4gzhu&&Info: Kill Signal Sent to PID %d.\n", fl.l_pid);
        }
        else 
            fprintf (stderr, "bbs4gzhu&&Info: Program not running.\n");
        exit (EXIT_FAILURE);
    }


    //没有锁,则给文件加锁,否则返回锁着文件的进程pid
    if (fl.l_type == F_UNLCK) {
        flock_reg ();
        return 0;
    }

    return fl.l_pid;
}
static void
signal_interrupted (int signo)
{
    exit (EXIT_SUCCESS);
    exit_flag = 1;
    fprintf(stdout,"\nbbs4gzhu&&Info: Interrupted. \n");
}
static void show_usage()
{
	printf("auto online for bbs.gzhu.edu.cn \n\
options: \n \
	-b --background. run in background. mostly this is for service mode. \n\
	-e --exit. quit the running program in background \n\
	-i --interval value(in second). interval time between online request. default value is 15 seconds. \n\
	-h --help. show this usage message. \n\
	-c --cookiepath. specifies the file containing the cookies for online request. \n\
	-u --username. username for login in the bbs. \n\
	-p --password. md5 of the password, used for login in the bbs. \n\
	--host. host for auto online. default value is \"bbs.gzhu.edu.cn\" \n\
	--port. the port with site. default value is 80. \n");


}

static void 
init_arguments(int *argc, char ***argv)
{
    /* Option struct for progrm run arguments */
    static struct option long_options[] =
        {
        {"background",  no_argument,        &background,    'b'},       
        {"exit",      no_argument,  &exit_flag,              'e'},
        {"interval",         required_argument,  &interval,              'i'},
        {"help",         no_argument,  0,              'h'},
        {"cookiepath",         required_argument,  NULL,              'c'},
	{"username", required_argument, NULL, 'u'},
	{"password", required_argument, NULL, 'p'},
	{"host", required_argument, NULL, 2},
	{"port", required_argument, NULL, 1},
        {0, 0, 0, 0}
        };

    int c;
    while (1) {

        /* getopt_long stores the option index here. */
        int option_index = 0;
        c = getopt_long ((*argc), (*argv), "bei:hc:u:p:",
                        long_options, &option_index);
        if (c == -1)
            break;
        switch (c) {
            case 0:
               break;
            case 'b':
                background = 1;
                break;
            case 'e':
                exit_flag = 1;
                break;
	    case 'i':
                interval = atoi(optarg);
                break;
            case 'h':
                show_usage();
                exit(EXIT_SUCCESS);
                break;
	    case 'c':
		cookiepath = optarg;
		break;
	    case 'u':
		strncpy(username, optarg, USERNAME_SIZE);
		break;
	    case 'p':
		strncpy(password, optarg, PASSWORD_SIZE);
		break;
	    case 2:
		host = optarg;
		break;
	    case 1:
		port = atoi(optarg);
		break;
            case '?':               
                exit(EXIT_FAILURE);
                break;
            default:
                fprintf (stderr,"Unknown option character `\\x%x'.\n", c);
                exit(EXIT_FAILURE);
        }
    }
}

void PANIC(char *msg);
#define PANIC(msg)  {perror(msg); abort();}
int getitem(const char *str, char *buffer, const int size, const char *start, const char end);

int tcp_connect(const char *host, const short port);
struct sockaddr_in getaddr(const char *host, const short port);
void loadcookies(const char *filename, char *buffer, const int size);
int 
code_convert(char *from_charset, char *to_charset,
             char *inbuf, size_t inlen, char *outbuf, size_t outlen);

int parse_username(const char *str, char *buffer, const int size);
int parse_formhash(const char *str, char *buffer, const int size);
int parse_sid(const char *str, char *buffer, const int size);
int parse_auth(const char *str, char *buffer, const int size);
int parse_parse_cookies(const char *str, char *buffer, const int size);
int parse_welcome_msg(const char *str, char *buffer, const int size);
int parse_return_msg(const char *str, char *buffer, const int size);
int parse_error_msg(const char *str, char *buffer, const int size);

int login(const char *username, const char *password, char *cookies, const int size);
int send_request(const int sockfd, const char *url, const char *header, const char *data, char *buffer, const int size);
int check_http(const char *response, const int size);
int online(const char *cookies);
char *gettime();

int
main(int argc, char *argv[])
{
	int ins_pid;
	char cookies[BUFFER_SIZE];

	init_arguments(&argc, &argv);

	lockfile = open (LOCKFILE, O_RDWR | O_CREAT , LOCKMODE);
	if (lockfile < 0){
		perror ("Lockfile");
		exit(EXIT_FAILURE);
	}

	if ( (ins_pid = is_running()) ) {
		fprintf(stderr,"bbs4gzhu@@ERROR: Program already "
				    "running with PID %d\n", ins_pid);
		exit(EXIT_SUCCESS);
	}

	signal (SIGINT, signal_interrupted);
	signal (SIGTERM, signal_interrupted);

	bzero(cookies, sizeof(cookies));
	if(strlen(cookiepath) > 0) {
		loadcookies(cookiepath, cookies, sizeof(cookies));
		if(strlen(username) <= 0) {
			if(parse_username(cookies, username, sizeof(username)) <= 0) {
				if(parse_sid(cookies, username, sizeof(username)) <= 0) {
					strcpy(username, "unknown");
				}
			}
		}
	} else {
		if(strlen(username) <= 0) {
			strcpy(username, "nobody");
		}
	}

	printf("current username: %s \n", username);

	if(background)    daemon_init();

	while(1) {
		printf("%s logging...", gettime());
		fflush(stdout);
		if(!login(username, password, cookies, sizeof(cookies))) {
			sleep(interval);
			continue;
		}
		printf("\n");
		while(online(cookies)) {
			printf("%s online...\r", gettime()); fflush(stdout);
			sleep(interval);
		}
		printf("%s offline...it will auto retrying!\n", gettime());
	}

	return 0;
}/* ----------  end of function main  ---------- */
char *gettime()
{
	static char str[64];
	struct tm *local;
	time_t t;
	t = time(NULL);
	local=localtime(&t);
	sprintf(str, "%02d:%02d:%02d", local->tm_hour, local->tm_min, local->tm_sec);
	return str;
}
int check_http(const char *response, const int size)
{
	char buffer[16];
	if(size <= 16) return 0;
	if(strstr(response, "HTTP/1.1 200 OK\r\n") == NULL) {
		strncpy(buffer, response, 15);
		buffer[15] = 0;
		printf("%s bad status:%s\n", username, buffer);
		return 0;
	}
	return 1;
}

void loadcookies(const char *filename, char *buffer, const int size)
{
	int bytes_read;
	FILE *fd = fopen(filename, "r");
	if(fd == NULL) {
		PANIC("loadcookies");
	}
	bytes_read = fread(buffer, 1, size, fd);
	buffer[bytes_read - 1] = 0;
	
	while(bytes_read--) {
		if(buffer[bytes_read] == '\r') buffer[bytes_read] = ' ';
		if(buffer[bytes_read] == '\n') buffer[bytes_read] = ' ';
	}
	
	fclose(fd);
}

int send_request(const int sockfd, const char *url, const char *header, const char *data, char *buffer, const int size) 
{
	int bytes_read = 0;
	char request_buffer[BUFFER_SIZE];
	if(data != NULL) {
		sprintf(request_buffer, "POST %s HTTP/1.1\r\nHost: %s:%d\r\nReferer: http://%s\r\nContent-Type: application/x-www-form-urlencoded\r\nContent-Length: %d\r\n%s\r\n\r\n%s", url, host, port, host, strlen(data), header, data);
	} else {
		sprintf(request_buffer, "GET %s HTTP/1.1\r\nHost: %s:%d\r\nReferer: http://%s\r\n%s\r\n", url, host, port, host, header);
	}

	//printf("%s\n", request_buffer);

	/* 发送数据 */
	send(sockfd, request_buffer, strlen(request_buffer), 0);

	/* 接收缓存 */
	bzero(buffer, sizeof(size));

	/* 接收 */
	bytes_read = recv(sockfd, buffer, size, 0);

	//printf("%s\n", buffer);

	return bytes_read;
}

int login(const char *username, const char *password, char *cookies, const int size) 
{
	int sockfd;
	int bytes_read;
	char buffer[BUFFER_SIZE];
	char header[BUFFER_SIZE];
	char formhash[FORMHASH_SIZE];
	char formdata[BUFFER_SIZE];
	char sid[SID_SIZE];
	char auth[AUTH_SIZE];
	char msg[BUFFER_SIZE];

	/* 先获取登录页面 */
	sockfd = tcp_connect(host, port);
	bytes_read = send_request(sockfd, "/logging.php?action=login&inajax=1", "", NULL, buffer, sizeof(buffer));	
	close(sockfd);
	if(check_http(buffer, bytes_read) == 0) return 0;
//	printf("%s\n", buffer);
	
	/* 若被列入黑名单,则等待3分钟后再试 */
	if(strlen(strstr(buffer, "\r\n\r\n")+4) <= 120) {//这个值一般在99左右。
		bytes_read = parse_error_msg(buffer, msg, sizeof(msg));
		if(bytes_read > 0 && strstr(msg, "\n") == NULL) {
			printf("Error:%s . Try 15m later..\r", msg);	
		} else {
			printf("Error:unknown. Try 3 minute later..\r", msg);
		}
		fflush(stdout);
		sleep(3*60);
		return 0;
	}
	/* 解析formhash */
	bytes_read = parse_formhash(buffer, formhash, sizeof(formhash));
	if(bytes_read <= 0) return 0;

	/* 解析SID */
	bytes_read = parse_sid(buffer, sid, sizeof(sid));
	if(bytes_read <= 0) return 0;

	strcat(cookies, "hLR_sid=");	strcat(cookies, sid);	strcat(cookies, ";");

	/* 构造header */
	sprintf(header, "Cookie: %s\r\n", cookies);

	/* 构造登录表单 */
	sprintf(formdata, "formhash=%s&loginfield=username&username=%s&password=%s&questionid=0&answer=&cookietime=2592000", formhash, username, password);

//	printf("%s %s\n", header, formdata);
	
	/* 提交登录请求 */
	sockfd = tcp_connect(host, port);
	bytes_read = send_request(sockfd, "/logging.php?action=login&loginsubmit=yes&inajax=1", header, formdata, buffer, sizeof(buffer));
	close(sockfd);
	if(check_http(buffer, bytes_read) == 0) return 0;

	/* 解析欢迎消息 */
	bytes_read = parse_welcome_msg(buffer, msg, sizeof(msg));
	if(bytes_read <= 0)  {
		/* 解析登录返回信息 */
		bytes_read = parse_return_msg(buffer, msg, sizeof(msg));
		if(bytes_read > 0) printf("Failed Info:%s\r", msg);
		return 0;
	}
	printf("Login Info:%s\r", msg);
	fflush(stdout);

	/* 解析auth */
	bytes_read = parse_auth(buffer, auth, sizeof(auth));
	if(bytes_read <= 0) return 0;	
	strcat(cookies, "hLR_auth=");	strcat(cookies, auth);	strcat(cookies, ";");

	/* 有效时间 */
	strcat(cookies, "hLR_cookietime=2592000;");

	return strlen(cookies);
}

int online(const char *cookies)
{
	int sockfd;
	int bytes_read;
	char buffer[BUFFER_SIZE];
	char header[BUFFER_SIZE];

	/* 构造header */
	sprintf(header, "Cookie: %s\r\n", cookies);

	/* 刷新页面保持在线 */
	sockfd = tcp_connect(host, port);
	bytes_read = send_request(sockfd, "/search.php", header, NULL, buffer, sizeof(buffer));	
	close(sockfd);
	if(check_http(buffer, bytes_read) == 0) return 0;
	
	/* 检测用户凭据是否到期 */
	if(strstr(buffer, "logging.php?action=logout") == NULL) return 0;

	return 1;
}

int parse_error_msg(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "![CDATA[", ']');
}

int parse_username(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "uchome_loginuser=", ';');
}

int parse_formhash(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "name=\"formhash\" value=\"", '\"');
}

int parse_sid(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "hLR_sid=", ';');
}

int parse_auth(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "hLR_auth=", ';');
}

int parse_cookies(const char *str, char *buffer, const int size)
{
	return	getitem(str, buffer, size, "Set-Cookie: ", ';');	
}

int parse_welcome_msg(const char *str, char *buffer, const int size)
{
	return getitem(str, buffer, size, "$('messageleft').innerHTML = '", '\'');	
}


int parse_return_msg(const char *str, char *buffer, const int size)
{
	return getitem(str, buffer, size, "<em id=\"returnmessage\">", '<');	
}


int getitem(const char *str, char *buffer, const int size, const char *start, const char end)
{
	int i;
	char *p = strstr(str, start);
	if(p == NULL) return 0;

	for(i = 0, p+= strlen(start); p[i] &&  i < (size - 1); i++) {
		if(p[i] == end) break;
		buffer[i] = p[i];
	}
	buffer[i] = '\0';
	return i;
}



struct sockaddr_in getaddr(const char *host, const short port)
{
    struct sockaddr_in sin;
    struct hostent *hosts = NULL;

    bzero(&sin, sizeof(struct sockaddr_in));
    sin.sin_family = AF_INET;
    sin.sin_port = htons(port);
    if(inet_addr(host) == INADDR_NONE) {
        hosts = gethostbyname(host);
	if(hosts != NULL) {
	    sin.sin_addr = *((struct in_addr*)hosts->h_addr);
	}
    } else {
	sin.sin_addr.s_addr = inet_addr(host);
    }
    return sin;
}

int
tcp_connect(const char *host, const short port)
{

    int     sockfd;
    struct sockaddr_in endpoint;

    endpoint = getaddr(host, port);
  
    sockfd = socket(AF_INET, SOCK_STREAM, 0);

    if (sockfd < 0) return 0;

    if (connect(sockfd, (struct sockaddr*)&endpoint, sizeof(struct sockaddr_in)) != 0) {
	close(sockfd); 
	return 0;
    }

    return (sockfd);
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  code_convert
 *  Description:  字符串编码转换
 * =====================================================================================
 */
int 
code_convert(char *from_charset, char *to_charset,
             char *inbuf, size_t inlen, char *outbuf, size_t outlen)
{
    memcpy(outbuf, inbuf, inlen < outlen ? inlen : outlen);
/*
    iconv_t cd;

    cd = iconv_open(to_charset,from_charset);

    if (cd==0) 
      return -1;
    memset(outbuf,0,outlen);

    if (iconv (cd, &inbuf, &inlen, &outbuf, &outlen)==-1) 
      return -1;
    iconv_close(cd);
*/
    return 0;
}


一个合并bib文件的小工具

因为当写过两篇文章之后,偶尔来个汇报之类的,就需要将之前文章的参考文献汇集在一起处理。然而这些文献本身可能是大量重复的,如何将多个bib文件中的重复文献去掉,仅保留不重复的部分,并最终输出到一个合并之后的bib文件中,是写这个小工具的一个背景。

原来的bib文件已经有自己的citation key,而且自己也习惯于这样的生成方式。虽然有一些文献管理软件也有此功能,但有如下弊端:

1)基于title来去重,而不是citation key去重;
2)bib文件中的其他非文献信息会被清除掉;
3)导出后原来的citation key无法保持原样

考虑到以上因素,所以就写了这个小工具:https://github.com/tpu01yzx/BibtexParser

这个工具的用法很简单,主要是几个参数:

1) -O –output 设置合并后输出到的文件名,缺省是标准输出设备。
2) –onlyregular 是否只输出Reguler(类似article,book,misc之类表示具体的文献记录,而非辅助信息如comment, string)的记录,默认为否。
3) –outputplain 是否输出非@开头的记录,这类块大部分是注释或者用于格式控制的,默认为否。

当然了,仅有这个工具,用起来还是有点麻烦,所以最后送上一个Bat批处理文件,把这个批处理文件,bib合并小工具,以及要合并的所有bib文件放在同一个目录。执行这个批处理文件,就不用每次都去找命令行,对于大部分习惯了Windows的用户来说应该是件好事。

@echo off
SetLocal EnableDelayedExpansion

set allbib=_all.bib
set exec=bib_combiner.exe

echo @comment{this file is generated by BibtexParser.exe} > %allbib%
set list=
for  %%i in (*.bib) do ( 
	if not "%%i" == "%allbib%" (		
		set list=!list! "%%i"
	)
)
%exec% "%allbib%" %list% -O "%allbib%" -R
%exec% --help
set exec=
set allbib=
set list=
pause

给伸手党准备好了,Windows下的打包(包含上面提到的一个工具和一个批处理文件:bib_combiner.exe和一个run.bat),点击这里下载

一种二元序列的线性复杂度算法的实现

#include <stdio.h>
#include <memory.h>

#define MAXL (1000)

typedef unsigned char uchar;

void prints(const uchar *s, const int n)
{
    int i;
    for(i=0;i<n;i++) {printf("%u",s[i]);}
    printf("\n");
}

//implement the Berlekamp–Massey algorithm for binary sequences.
//Please see https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#The_algorithm_for_the_binary_field
int bm(const uchar*s, const int n)
{
    int i,j,lc,m,d;
    uchar b[MAXL];
    uchar c[MAXL];
    uchar t[MAXL];
    
    b[0]=1;c[0]=1;
    for(i=1;i<n;i++){b[i]=0;c[i]=0;};
  
    lc=0;m=-1;
    
    for(i=0;i<n;i++) {
        d=s[i];
        for(j=1;j<=lc;j++) { d ^=s[i-j] & c[j]; }
        if(d!=0){
            memcpy(t,c,n);
            for(j=0;j<n-i+m;j++) { c[i-m+j]^=b[j]; }
            
            if(2*lc<=i) {
                lc=i+1-lc;
                m=i;
                memcpy(b,t,n);
            }
        }
    }
  
    return lc;
}

int main()
{
    int n;
    int lc;
    char c;
    int i,j;
    uchar s[MAXL];
    uchar ans_s[MAXL];
    int ans_lc;
    int ans_j;
    
    //if you would like to read the sequence from file, please uncomment the follows line.
    //freopen ("s1.txt","r",stdin);
    //skip the first line
    while((c=getchar())!='\n');
    //read the sequence
    n=0;
    while(n<MAXL){
        c=getchar();
        //the line should be ended with '\n' or ']'.
        if(c=='\n' || c==']') break;
        
        //only '0' and '1' are captured.
        if(c>='0' && c<='1') {
            //convert '0' and '1' to 0 and 1.
            s[n++]=c-'0';
        }
    }
    prints(s,n);
    printf("There are %d bits.\n", n);
    
    lc = bm(s,n);
    printf("The original LC is %d\n", lc);
    
    //make sure that current ans_lc is big enough.
    ans_lc=n; ans_j=-1;
    for(i=0;i<n;i++) {
        s[i] ^=1;
        
        lc=bm(s,n);
        if(lc<ans_lc) {
            //save the current optimal answer;
            ans_lc=lc; ans_j=i;
            memcpy(ans_s,s,n);
            printf("Update ans with lc=%d when  s[%u]:%u->%u.\n", 
            ans_lc, ans_j, s[ans_j]^1, ans_s[ans_j]);
        }
        
        s[i] ^=1;
    }
    
    printf("The minimal 1+lc is %d when s[%u]:%u->%u.\n", 
        1+ans_lc, ans_j, s[ans_j], ans_s[ans_j]);
    prints(ans_s,n);
    
    
    return 0;
}

这是基于C语言实现的wiki上二元序列的线性复杂度,如果需要对应的极小多项式可以从最后的c变量数组中直接转换过来,这并不是什么有难度的事情。

VPN拨号后自动处理路由策略(For Windows)

经常使用各种不同的VPN,但一般客户端都需要根据不同的场景来选择配置不同的路由策略,很久之前写过一个批处理脚本(For Win)。今天突然要用,但是找不到了,所以只好重新再写一次,然后保存下来,希望下次会记得。

PS:Linux类系统下自然有更多优秀的解决方案,或者说第三方VPN插件自然也会很优雅的解决办法,自然不必纠结我这个批处理的脚本,只给有需要的人。

@echo off
Setlocal enabledelayedexpansion
rem 校内常见的私有地址,例如教务系统,OA办公系统等
set ip0=10.0.0.0/8;
set prefix=10.0.0.
rem =====================以上部分不要修改===========================================

rem 所有需要通过VPN访问的IP,用分号隔开。支持添加整个子网。最多添加到ip3,并且每个都要以分号结尾
set ip1=211.155.94.138;122.115.55.6;
set ip2=
set ip3=

rem 用户名user
set user=XXX

rem 密码pass
set pass=XXX

rem 新建vpn连接的名称,可以在"控制面板"的"网络连接"中看到
set vpn_name=gdst

rem =====================以下部分不要修改=================================
set ip4=172.16.0.0/16
set ipt="%ip0% %ip1% %ip2% %ip3% %ip4%"
set "ips=%ipt: =%"
set try=0
set mask=
set aip=
set ans=
set ip=

:dial
cls
echo 正在VPN连接...
rasdial %vpn_name% %user% %pass%
if errorlevel 1 (
set /a try+=1
echo 第%try%次拨号失败,5秒后重新尝试,按Ctrl+C终止
ping 1.1.1.1 -n 1 -w 5000 > nul
goto dial
) else (
echo 拨号成功.
)
rem VPN获取的IP地址应该是10.0.0开头的

for /f "tokens=1* delims=:" %%i in ('ipconfig /all^|find "%prefix%"') do (
if /i not "%%j" == "" (
set ip=%%j
goto ipout
)
)
:ipout
echo VPN的IP地址为:%ip%
echo 正在处理网络配置,如果失败,请修复本地连接后重新尝试。
rem 删除拨号成功后默认添加的路由
rem route delete 0.0.0.0 mask 0.0.0.0 %ip% METRIC 1 >NUL 2>NUL
call:clean
call:add_all %ips%
echo 网络配置完毕。

:menu
rem cls
rem echo 当前路由表为(仅供调试之用)
rem route print %prefix%
set /p user_input=输入1,将自动断开vpn,并恢复原来的网络配置。
if /i not "%user_input%"=="1" goto menu

rasdial %vpn_name% /DISCONNECT
call:clean
echo 操作完毕,请关闭此窗口。
pause
exit

:gmask
set /a nid=32
set /a q=4
set /a r=0
set aip=%~1
set "aip=%aip: =%"
if "!aip!" == "" goto:eof
for /f "delims=/, tokens=1,*" %%s in ("%~1") do (
if /i not "%%t"=="" (
set /a q="%%t/8"
set /a nid="%%t"
set aip=%%s
)
)

set /a r="%nid%-%q%*8"
if %nid% GEQ 32 (
set mask=255.255.255.255.
) else if %nid% LEQ 0 (
set mask=0.0.0.0.
) else (
set mask=
for /L %%i in (1,1,%q%) do (
set mask=!mask!255.
)
set /a next="%q%+1"
if %r% GTR 0 (
set /a smask=1"<<"%r% set /a smask=256-!smask! set mask=!mask!!smask!. ) for /L %%i in (!next!,1,4) do ( set mask=!%mask!0. ) ) set "mask=%mask:~0,-1%" goto:eof :add_all for /f "delims=;, tokens=1,*" %%i in ("%~1") do ( call:gmask "%%i" echo 正在处理 %%i !aip! !mask! %ip% if /i not "!aip!" == "" ( route add !aip! mask !mask! %ip% METRIC 1 >NUL 2>NUL
)
if /i not "%%j"=="" (
call:add_all "%%j"
)

)
goto:eof

:clean
for /f "tokens=1-4" %%i in ('route print ^| find "!ip!"') do (
route delete %%i mask %%j !ip! >NUL 2>NUL
)
goto:eof

执行后显示的日志信息如下:

正在VPN连接…
正在连接到 GDST…
正在验证用户名及密码…
正在网络上注册您的计算机…
已连接 GDST。
命令已完成。
拨号成功.
VPN的IP地址为: 10.0.0.4
正在处理网络配置,如果失败,请修复本地连接后重新尝试。
正在处理 10.0.0.0/8 10.0.0.0 255.0.0.0 10.0.0.4
正在处理 211.155.94.138 211.155.94.138 255.255.255.255 10.0.0.4
正在处理 122.115.55.6 122.115.55.6 255.255.255.255 10.0.0.4
正在处理 172.16.0.0/16 172.16.0.0 255.255.0.0 10.0.0.4
网络配置完毕。
输入1,将自动断开vpn,并恢复原来的网络配置。1
命令已完成。
操作完毕,请关闭此窗口。
请按任意键继续. . .