luocong's profile天空之城的点点滴滴的回忆PhotosBlogLists Tools Help

Blog


    November 17

    某公司的2006年内部评级题

    请将8个给定的正整数(如1,2,3,4,5,6,7,8)分别放在一个正方体的8个角的顶点上,以实现如下要求(如果可能):正方体六个面上的四个角点整数之和相等。输出结果如:A1=1, A2=2, ...

    算法分析:
    简单题,秒杀,因为数据范围不大,搜索即可。

    代码:

    #include <stdio.h>

    #define MAXN 8

    int a[MAXN + 1], b[MAXN], used[MAXN] = { 0 };

    void print()
    {
        int i;
        for (i = 1; i < MAXN; ++i)
            printf("A%d = %d ", i, a[i]);
        printf("A%d = %d\n", i, a[i]);
    }

    void judge()
    {
        int r1, r2, r3, r4, r5, r6;

        r1 = a[1] + a[2] + a[3] + a[4];
        r2 = a[1] + a[3] + a[5] + a[7];
        r3 = a[2] + a[4] + a[6] + a[8];
        r4 = a[1] + a[2] + a[5] + a[6];
        r5 = a[3] + a[4] + a[7] + a[8];
        r6 = a[5] + a[6] + a[7] + a[8];

        if (r1 == r2 && r2 == r3 && r3 == r4 && r4 == r5 && r5 == r6)
            print();
    }

    void search(const int depth)
    {
        int i;
        for (i = 0; i < MAXN; ++i)
        {
            if (!used[i])
            {
                used[i] = 1;

                a[depth] = b[i];
                if (depth == MAXN)
                    judge();
                else
                    search(depth + 1);

                used[i] = 0;
            }
        }
    }

    int main()
    {
        int i;

        for (i = 0; i < MAXN; ++i)
            scanf("%d", &b[i]);

        search(1);

        return 0;
    }
    June 07

    获得Idle进程的EPROCESS

    响应号召,关点技术的税。
     
    Idle是一个很特殊的进程,其进程号为0,如果在驱动中直接用PsLookupProcessByProcessId是无法得到它的EPROCESS的。翻阅盖子大叔给我们的Windows源代码,会发现可以用PsIdleProcess来获得它,但比较淫荡的是这个变量并没有被ntoskrnl导出,饿地神啊,难道又要用暴力搜索opcode大法?
     
    在这里提一个思路。先获得KPCR,然后通过KPCR中的KPRCB获得IdleThread的KTHREAD,再获得ApcState,其偏移0x10处就是Idle的EPROCESS了。怎么样很简单吧?自己动手,丰衣足食。收工。
    May 25

    PsLookupProcessByProcessId

    昨天为了这个破API蓝屏了一整天,估计达20次以上,特此纪念之。
     
    调试定位的过程极其痛苦,不过今天早上终于搞定,简单说说吧。调用完PsLookupProcessByProcessId之后记住要调用ObDereferenceObject,否则Object还会在内存中不被释放,进而导致调用这个API的进程在“退出”后,会有两种状态:在User层的状态是退出了,但在Kernel层的状态还是deleting(用softice的proc命令可以看到),这样当下次再访问这个进程的内存的时候就会蓝屏。奇怪的是在WinXP下才会这样,Win2000中貌似没事,不知道是巧合还是操作系统做了点什么手脚?(这也从另一个侧面反映出Win2000其实不够健壮),懒得细究了,反正弄清楚了也没法维护世界的和平。
     
    源码之前,了无秘密。(private\ntos\ps\pscid.c)
     
    NTSTATUS
    PsLookupProcessByProcessId(
        IN HANDLE ProcessId,
        OUT PEPROCESS *Process
        )
     
    /*++
     
    Routine Description:
     
        This function accepts the process id of a process and returns a
        referenced pointer to the process.
     
    Arguments:
     
        ProcessId - Specifies the Process ID of the process.
     
        Process - Returns a referenced pointer to the process specified by the
            process id.
     
    Return Value:
     
        STATUS_SUCCESS - A process was located based on the contents of
            the process id.
     
        STATUS_INVALID_PARAMETER - The process was not found.
     
    --*/
     
    {
     
        PHANDLE_TABLE_ENTRY CidEntry;
        PEPROCESS lProcess;
        NTSTATUS Status;
     
        CidEntry = ExMapHandleToPointer(PspCidTable, ProcessId);
        Status = STATUS_INVALID_PARAMETER;
        if (CidEntry != NULL) {
            lProcess = (PEPROCESS)CidEntry->Object;
            if (lProcess != (PEPROCESS)PSP_INVALID_ID && lProcess->Pcb.Header.Type == ProcessObject && lProcess->GrantedAccess ) {
                ObReferenceObject(lProcess);
                *Process = lProcess;
                Status = STATUS_SUCCESS;
            }
     
            ExUnlockHandleTableEntry(PspCidTable, CidEntry);
        }
     
        return Status;
    }
     
    是由代码中的这行:
                ObReferenceObject(lProcess);
    导致的。
    February 23

    对语言的一些看法@2006-02-23

    今天继续废代码,一堆一堆的代码被自己废掉改写,不过一点都不心疼,因为改写之后的整个框架更加清晰明了&&易于维护,也更能适应将来可能出现的不可预料的情况了。以前一直不屑于设计模式,昨晚心血来潮,看了两个模式:Facade和Adapter,惊讶地发现这两个星期以来废掉之后重写的代码居然就是符合这两个模式的,一下子就理解了,有种顿悟的快感。
     
    C/C++程序员要过的第一关往往是硬件关,因为C/C++设计之初天生就是与硬件底层相吻合的,也正因为如此,它们非常适合用来写数据结构。但这往往会令C/C++程序员过于注重代码或硬件细节(没办法的事情,不掌握硬件的话根本没法玩转C/C++),以至于对设计模式等东西关注甚少。再看看Java程序员,由于Java封装了底层的细节,因此该语言的使用者一开始就不必拘泥于一个字节有多长之类的东西,而能够把精力转移到比较高层的角度来思考问题。所以在讨论设计模式的社团中,Java程序员的数量远远高于C/C++。学了半年Java的程序员可能就能对各种模式评头品足了,但对于C/C++的学习者,半年时间能完全掌握指针就不错了。简单说来,C/C++程序员更注重运行时效率,Java程序员更注重开发时效率,忘了以前在哪里看过这么一句话:“如果一个新的模式能把开发效率提高10%,但会导致程序的运行效率降低10%,那么C/C++社团一定会强烈反对其加入标准,但Java社团一定会强烈赞成。”,现在想想貌似有点道理。
     
    笔者一直不喜欢对语言发表评论的,尤其是这种××语言和××语言的对比,毫无意义。保证这是最后一次,请欲吵架和扔砖者自重,寒,闪。
    November 21

    KMP

    以前懂KMP的,一段时间后居然看不懂了,郁闷……花费了一个星期的晚上来看懂算法、写代码,直到今晚终于把它写出来了,记录一下将来应该用得上:
     
    ////////////////////////////////////////////////////////////////////////////////
    //
    //  FileName    :   KMP.c
    //  Version     :   0.10
    //  Author      :   Luo Cong
    //  Date        :   2005-11-21 19:15:31
    //  Comment     :  
    //
    ////////////////////////////////////////////////////////////////////////////////
     
    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
     
    static void kmp_get_next(const int patternlen, const char *pattern, int next[])
    {
        int i = 0;
        int j = -1;
     
        next[0] = -1;
        while (i < patternlen - 1)
        {
            if (-1 == j || pattern[i] == pattern[j])
            {
                ++i;
                ++j;
                if (pattern[i] != pattern[j])
                    next[i] = j;
                else
                    next[i] = next[j];
            }
            else
                j = next[j];
        }
    }
     
    char * kmp_search(const char *text, const char *pattern)
    {
        int i = 0;
        int j = 0;
        int textlen;
        int patternlen;
        int *next = NULL;
     
        textlen = strlen(text);
        patternlen = strlen(pattern);
     
        next = (int *)malloc(patternlen * sizeof(int));
        if (NULL == next)
            return NULL;
     
        kmp_get_next(patternlen, pattern, next);
     
        while (i < textlen && j < patternlen)
        {
            if (-1 == j || text[i] == pattern[j])
            {
                ++i;
                ++j;
            }
            else
                j = next[j];
        }
     
        free(next);
        next = NULL;
     
        if (j >= patternlen)
            return (char *)&text[i - patternlen];
        else
            return NULL;
    }
     
    int main(int argc, char *argv[])
    {
        char *text = "acabaabcaabaabcac";
        char *pattern = "abaabcac";
        char *pDest = NULL;
     
        printf("Text    : %s\nPattern : %s\n", text, pattern);
        pDest = kmp_search(text, pattern);
        if (pDest)
            printf("Pattern found at position : %d\n", pDest - text + 1);
        else
            printf("Pattern NOT found!\n");
    }
     
    太累的缘故偶就不对代码进行注释和解释了,建议自己拿笔推算一次next函数,应该就能明白算法了。在这里要稍微鄙视一下严奶奶的数据结构C语言版的PPT(我手头没书,只好看PPT了),因为其数组的下标居然是从1开始的,这里让我想了半天都没想明白,浪费了不少时间;而且其字符串的第一个元素表示的是字符串的长度——很明显就是从Pascal中直接搬过来的代码。
     
    另外需要补充的是,由于KMP对于待匹配的字符串是不需要回溯的(而只要对pattern进行回溯),因此可以用于对流的匹配。不过上面的代码还不能直接用于流匹配,我懒得改了,以后要用到的时候再说吧。