1/* 2 * ntfs_collate.c - NTFS kernel collation handling. 3 * 4 * Copyright (c) 2006-2008 Anton Altaparmakov. All Rights Reserved. 5 * Portions Copyright (c) 2006-2008 Apple Inc. All Rights Reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright notice, 11 * this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright notice, 13 * this list of conditions and the following disclaimer in the documentation 14 * and/or other materials provided with the distribution. 15 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its 16 * contributors may be used to endorse or promote products derived from this 17 * software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 23 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * ALTERNATIVELY, provided that this notice and licensing terms are retained in 31 * full, this file may be redistributed and/or modified under the terms of the 32 * GNU General Public License (GPL) Version 2, in which case the provisions of 33 * that version of the GPL will apply to you instead of the license terms 34 * above. You can obtain a copy of the GPL Version 2 at 35 * http://developer.apple.com/opensource/licenses/gpl-2.txt. 36 */ 37 38#include <kern/debug.h> 39 40#include <string.h> 41 42#include "ntfs_collate.h" 43#include "ntfs_debug.h" 44#include "ntfs_endian.h" 45#include "ntfs_layout.h" 46#include "ntfs_unistr.h" 47#include "ntfs_volume.h" 48 49/** 50 * ntfs_collate_binary - byte by byte binary collation 51 * 52 * Used for COLLATION_BINARY and COLLATION_NTOFS_SID. 53 */ 54static int ntfs_collate_binary(ntfs_volume *vol, 55 const void *data1, const int data1_len, 56 const void *data2, const int data2_len) 57{ 58 int len, rc; 59 60 ntfs_debug("Entering."); 61 len = data1_len; 62 if (data2_len < data1_len) 63 len = data2_len; 64 rc = memcmp(data1, data2, len); 65 if (!rc && (data1_len != data2_len)) { 66 /* 67 * If @len equals @data1_len this implies that @data1_len is 68 * smaller than @data2_len. 69 */ 70 if (len == data1_len) 71 rc = -1; 72 else 73 rc = 1; 74 } 75 ntfs_debug("Done (returning %d).", rc); 76 return rc; 77} 78 79/** 80 * ntfs_collate_filename - filename collation 81 * 82 * Used for COLLATION_FILENAME. 83 * 84 * Note: This only performs exact matching as it is only intended to be used 85 * when looking up a particular name that is already known to exist and we just 86 * want to locate the correct index entry for it so that we can modify/delete 87 * it. Alternatively, we want to add a new name and we already know that it 88 * does not exist in the index so we just want to locate the correct index 89 * entry in front of which we need to insert the name. 90 */ 91static int ntfs_collate_filename(ntfs_volume *vol, 92 const void *data1, const int data1_len, 93 const void *data2, const int data2_len) 94{ 95 const FILENAME_ATTR *fn1 = data1; 96 const FILENAME_ATTR *fn2 = data2; 97 int rc; 98 99 ntfs_debug("Entering."); 100 if (data1_len < (int)sizeof(FILENAME_ATTR)) 101 panic("%s(): data1_len < sizeof(FILENAME_ATTR)\n", 102 __FUNCTION__); 103 if (data2_len < (int)sizeof(FILENAME_ATTR)) 104 panic("%s(): data2_len < sizeof(FILENAME_ATTR)\n", 105 __FUNCTION__); 106 /* 107 * We only care about exact matches, however in order to do proper 108 * collation we need to do the case insensitive check first because the 109 * upcased characters will not necessarily collate in the same order as 110 * the non-upcased ones. 111 */ 112 rc = ntfs_collate_names((ntfschar*)&fn1->filename, 113 fn1->filename_length, (ntfschar*)&fn2->filename, 114 fn2->filename_length, 1, FALSE, vol->upcase, 115 vol->upcase_len); 116 if (!rc) 117 rc = ntfs_collate_names((ntfschar*)&fn1->filename, 118 fn1->filename_length, (ntfschar*)&fn2->filename, 119 fn2->filename_length, 1, TRUE, 120 vol->upcase, vol->upcase_len); 121 ntfs_debug("Done (returning %d).", rc); 122 return rc; 123} 124 125/** 126 * ntfs_collate_ntofs_ulongs - le32 by le32 collation 127 * 128 * Used for COLLATION_NTOFS_ULONG, COLLATION_NTOFS_ULONGS, and 129 * COLLATION_NTOFS_SECURITY_HASH. 130 */ 131static int ntfs_collate_ntofs_ulongs(ntfs_volume *vol, 132 const void *data1, const int data1_len, 133 const void *data2, const int data2_len) 134{ 135 const le32 *p1 = data1; 136 const le32 *p2 = data2; 137 int min_len, i, rc; 138 139 ntfs_debug("Entering."); 140 if (data1_len & (sizeof(u32) - 1)) 141 panic("%s(): data1_len & (sizeof(u32) - 1)\n", __FUNCTION__); 142 if (data2_len & (sizeof(u32) - 1)) 143 panic("%s(): data2_len & (sizeof(u32) - 1)\n", __FUNCTION__); 144 min_len = data1_len; 145 if (min_len > data2_len) 146 min_len = data2_len; 147 min_len >>= 2; 148 for (i = 0; i < min_len; i++) { 149 const u32 u1 = le32_to_cpu(p1[i]); 150 const u32 u2 = le32_to_cpu(p2[i]); 151 if (u1 > u2) { 152 rc = 1; 153 goto out; 154 } 155 if (u1 < u2) { 156 rc = -1; 157 goto out; 158 } 159 } 160 rc = 1; 161 if (data1_len < data2_len) 162 rc = -1; 163 else if (data1_len == data2_len) 164 rc = 0; 165out: 166 ntfs_debug("Done (returning %d).", rc); 167 return rc; 168} 169 170typedef int (*ntfs_collate_func_t)(ntfs_volume *, const void *, const int, 171 const void *, const int); 172 173static ntfs_collate_func_t ntfs_do_collate0x0[3] = { 174 ntfs_collate_binary, /* COLLATION_BINARY */ 175 ntfs_collate_filename, /* COLLATION_FILENAME */ 176 NULL, /* COLLATION_UNICODE_STRING */ 177}; 178 179static ntfs_collate_func_t ntfs_do_collate0x1[4] = { 180 ntfs_collate_ntofs_ulongs, /* COLLATION_NTOFS_ULONG */ 181 ntfs_collate_binary, /* COLLATION_NTOFS_SID */ 182 ntfs_collate_ntofs_ulongs, /* COLLATION_NTOFS_SECURITY_HASH */ 183 ntfs_collate_ntofs_ulongs, /* COLLATION_NTOFS_ULONGS */ 184}; 185 186/** 187 * ntfs_collate - collate two data items using a specified collation rule 188 * @vol: ntfs volume to which the data items belong 189 * @cr: collation rule to use when comparing the items 190 * @data1: first data item to collate 191 * @data1_len: length in bytes of @data1 192 * @data2: second data item to collate 193 * @data2_len: length in bytes of @data2 194 * 195 * Collate the two data items @data1 and @data2 using the collation rule @cr 196 * and return -1, 0, ir 1 if @data1 is found, respectively, to collate before, 197 * to match, or to collate after @data2. 198 * 199 * For speed we use the collation rule @cr as an index into two tables of 200 * function pointers to call the appropriate collation function. 201 */ 202int ntfs_collate(ntfs_volume *vol, COLLATION_RULE cr, 203 const void *data1, const int data1_len, 204 const void *data2, const int data2_len) { 205 int i; 206 207 i = le32_to_cpu(cr); 208 ntfs_debug("Entering (collation rule 0x%x, data1_len 0x%x, data2_len " 209 "0x%x).", i, data1_len, data2_len); 210 /* 211 * TODO: At the moment we do not support COLLATION_UNICODE_STRING so we 212 * BUG() for it. 213 */ 214 if (cr == COLLATION_UNICODE_STRING) 215 panic("%s(): cr == COLLATION_UNICODE_STRING\n", __FUNCTION__); 216 if (i < 0) 217 panic("%s(): i < 0\n", __FUNCTION__); 218 if (i <= 0x02) 219 return ntfs_do_collate0x0[i](vol, data1, data1_len, 220 data2, data2_len); 221 if (i < 0x10) 222 panic("%s(): i < 0x10\n", __FUNCTION__); 223 i -= 0x10; 224 if (i <= 3) 225 return ntfs_do_collate0x1[i](vol, data1, data1_len, 226 data2, data2_len); 227 panic("%s(): i > 3\n", __FUNCTION__); 228 return 0; 229} 230