hfs_unicompare.c

linux下开发的针对所有磁盘的数据恢复的源码

/*
** The Sleuth Kit
**
** This software is subject to the IBM Public License ver. 1.0,
** which was displayed prior to download and is included in the readme.txt
** file accompanying the Sleuth Kit files.  It may also be requested from:
** Crucial Security Inc.
** 14900 Conference Center Drive
** Chantilly, VA 20151
**
** Judson Powers [[e-mail]]
** Copyright (c) 2008 ATC-NY.  All rights reserved.
** This file contains data developed with support from the National
** Institute of Justice, Office of Justice Programs, U.S. Department of Justice.
*/

/*
** You may distribute the Sleuth Kit, or other software that incorporates
** part of all of the Sleuth Kit, in object code form under a license agreement,
** provided that:
** a) you comply with the terms and conditions of the IBM Public License
**    ver 1.0; and
** b) the license agreement
**     i) effectively disclaims on behalf of all Contributors all warranties
**        and conditions, express and implied, including warranties or
**        conditions of title and non-infringement, and implied warranties
**        or conditions of merchantability and fitness for a particular
**        purpose.
**    ii) effectively excludes on behalf of all Contributors liability for
**        damages, including direct, indirect, special, incidental and
**        consequential damages such as lost profits.
**   iii) states that any provisions which differ from IBM Public License
**        ver. 1.0 are offered by that Contributor alone and not by any
**        other party; and
**    iv) states that the source code for the program is available from you,
**        and informs licensees how to obtain it in a reasonable manner on or
**        through a medium customarily used for software exchange.
**
** When the Sleuth Kit or other software that incorporates part or all of
** the Sleuth Kit is made available in source code form:
**     a) it must be made available under IBM Public License ver. 1.0; and
**     b) a copy of the IBM Public License ver. 1.0 must be included with
**        each copy of the program.
*/

// Adapted from Apple's Tech Note 1150

//
//  FastUnicodeCompare - Compare two Unicode strings; produce a relative ordering
//
//      IF              RESULT
//  --------------------------
//  str1 < str2     =>  -1
//  str1 = str2     =>   0
//  str1 > str2     =>  +1
//
//  The lower case table starts with 256 entries (one for each of the upper bytes
//  of the original Unicode char).  If that entry is zero, then all characters with
//  that upper byte are already case folded.  If the entry is non-zero, then it is
//  the _index_ (not byte offset) of the start of the sub-table for the characters
//  with that upper byte.  All ignorable characters are folded to the value zero.
//
//  In pseudocode:
//
//      Let c = source Unicode character
//      Let table[] = lower case table 
//
//      lower = table[highbyte(c)]
//      if (lower == 0)
//          lower = c
//      else
//          lower = table[lower+lowbyte(c)]
//
//      if (lower == 0)
//          ignore this character
//
//  To handle ignorable characters, we now need a loop to find the next valid
//  character.  Also, we can't pre-compute the number of characters to compare;
//  the string length might be larger than the number of non-ignorable characters.
//  Further, we must be able to handle ignorable characters at any point in the
//  string, including as the first or last characters.  We use a zero value as a
//  sentinel to detect both end-of-string and ignorable characters.  Since the File
//  Manager doesn't prevent the NUL character (value zero) as part of a filename,
//  the case mapping table is assumed to map u+0000 to some non-zero value (like
//  0xFFFF, which is an invalid Unicode character).
//
//  Pseudocode:
//
//      while (1) {
//          c1 = GetNextValidChar(str1)         //  returns zero if at end of string
//          c2 = GetNextValidChar(str2)
//
//          if (c1 != c2) break                 //  found a difference
//
//          if (c1 == 0)                        //  reached end of string on both
//                                              //  strings at once?
//              return 0;                       //  yes, so strings are equal
//      }
//
//      // When we get here, c1 != c2.  So, we just need to determine which one is
//      // less.
//      if (c1 < c2)
//          return -1;
//      else
//          return 1;
//

#include "tsk_fs_i.h"
#include "tsk_hfs.h"

static int hfs_unicode_compare_int(uint16_t endian, hfs_uni_str * uni1,
    hfs_uni_str * uni2);

int
hfs_unicode_compare(HFS_INFO * hfs, hfs_uni_str * uni1, hfs_uni_str * uni2)
{
    if (hfs->is_case_sensitive) {
        uint16_t l1, l2;
        uint8_t *s1, *s2;
        uint16_t c1, c2;

        l1 = tsk_getu16(hfs->fs_info.endian, uni1->length);
        l2 = tsk_getu16(hfs->fs_info.endian, uni2->length);
        s1 = uni1->unicode;
        s2 = uni2->unicode;

        while (1) {
            if ((l1 == 0) && (l2 == 0))
                return 0;
            if (l1 == 0)
                return -1;
            if (l2 == 0)
                return 1;
            c1 = tsk_getu16(hfs->fs_info.endian, s1);
            c2 = tsk_getu16(hfs->fs_info.endian, s2);
            if (c1 < c2)
                return -1;
            if (c1 > c2)
                return 1;
            s1 += 2;
            s2 += 2;
            --l1;
            --l2;
        }
    }
    else
        return hfs_unicode_compare_int(hfs->fs_info.endian, uni1, uni2);
}

extern uint16_t gLowerCaseTable[];

static int
hfs_unicode_compare_int(uint16_t endian, hfs_uni_str * uni1,
    hfs_uni_str * uni2)
{
    uint16_t c1, c2;
    uint16_t temp;
    uint16_t *lowerCaseTable;

    uint16_t length1, length2;
    uint8_t *str1 = uni1->unicode;
    uint8_t *str2 = uni2->unicode;

    length1 = tsk_getu16(endian, uni1->length);
    length2 = tsk_getu16(endian, uni2->length);

    lowerCaseTable = gLowerCaseTable;

    while (1) {
        //  Set default values for c1, c2 in case there are no more valid chars
        c1 = 0;
        c2 = 0;
        //  Find next non-ignorable char from str1, or zero if no more
        while (length1 && c1 == 0) {
            c1 = tsk_getu16(endian, str1);
            str1 += 2;
            --length1;
            if ((temp = lowerCaseTable[c1 >> 8]) != 0)  //  is there a subtable
                //  for this upper byte?
                c1 = lowerCaseTable[temp + (c1 & 0x00FF)];      //  yes, so fold the char
        }
        //  Find next non-ignorable char from str2, or zero if no more
        while (length2 && c2 == 0) {
            c2 = tsk_getu16(endian, str2);
            str2 += 2;
            --length2;
            if ((temp = lowerCaseTable[c2 >> 8]) != 0)  //  is there a subtable
                //  for this upper byte?
                c2 = lowerCaseTable[temp + (c2 & 0x00FF)];      //  yes, so fold the char
        }
        if (c1 != c2)           //  found a difference, so stop looping
            break;
        if (c1 == 0)            //  did we reach the end of both strings at the same time?
            return 0;           //  yes, so strings are equal
    }
    if (c1 < c2)
        return -1;
    else
        return 1;
}