common.cpp

A*算法 A*算法 A*算法 A*算法A*算法A*算法

/*
 *  common.c -- shared functions used by mpq-tools.
 *
 *  Copyright (C) 2003 Maik Broemme <[e-mail]>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 *  $Id: common.cpp,v 1.1 2005/04/09 22:09:18 ufoz Exp $
 */

#include <sys/stat.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include "libmpq/mpq.h"
#include "libmpq/common.h"

/*
 *  This function decrypts a MPQ block.
 */
int libmpq_decrypt_block(mpq_archive *mpq_a, unsigned int *block, unsigned int length, unsigned int seed1) 
{
	unsigned int seed2 = 0xEEEEEEEE;
	unsigned int ch;

	/* Round to unsigned int's */
	length >>= 2;
	while (length-- > 0) {
		seed2    += mpq_a->buf[0x400 + (seed1 & 0xFF)];
		ch        = *block ^ (seed1 + seed2);
		seed1     = ((~seed1 << 0x15) + 0x11111111) | (seed1 >> 0x0B);
		seed2     = ch + seed2 + (seed2 << 5) + 3;
		*block++  = ch;
	}
	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This function hashes a string to a hash code.
 *  *o1 and *o2 will contain the resulting values.
 * type 1 and 2 are used for hashing filenames, type 3 for hashing the key that encrypts the hash table,
 * and type 4 for encrypting the actual data.
 */
unsigned int libmpq_hash_string(mpq_archive *mpq_a, unsigned int type, const unsigned char *pbKey) {
	unsigned int seed1 = 0x7FED7FED;
	unsigned int seed2 = 0xEEEEEEEE;
	unsigned int ch;			/* One key character */

	/* Prepare seeds */
	while (*pbKey != 0) {
		ch = toupper(*pbKey++);
		seed1 = mpq_a->buf[(type<<8) + ch] ^ (seed1 + seed2);
		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
	}
	
	return seed1;
}
/*
 *  This function decrypts the hashtable for the
 *  file informations.
 */
int libmpq_decrypt_hashtable(mpq_archive *mpq_a, unsigned char *pbKey) {
	unsigned int seed1, seed2;
    unsigned int ch;			/* One key character */
	unsigned int *pdwTable = (unsigned int *)(mpq_a->hashtable);
	unsigned int length = mpq_a->header->hashtablesize * 4;

	/* Decrypt it */
    seed1 = libmpq_hash_string(mpq_a, 3, pbKey);
	seed2 = 0xEEEEEEEE;
	while (length-- > 0) {
		seed2 += mpq_a->buf[0x400 + (seed1 & 0xFF)];
		ch     = *pdwTable ^ (seed1 + seed2);
		seed1  = ((~seed1 << 0x15) + 0x11111111) | (seed1 >> 0x0B);
		seed2  = ch + seed2 + (seed2 << 5) + 3;
		*pdwTable++ = ch;
	}
	return LIBMPQ_TOOLS_SUCCESS;
}


/*
 *  This function hashes a filename to a hash code.
 *  *o1 and *o2 will contain the resulting values.
 */
int libmpq_hash_filename(mpq_archive *mpq_a, const unsigned char *pbKey, unsigned int *o1, unsigned int *o2) {
	//unsigned int seed1, seed2, seed3, seed4;

	*o1 = libmpq_hash_string(mpq_a, 1, pbKey);
	*o2 = libmpq_hash_string(mpq_a, 2, pbKey);

	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This function decrypts the blocktable.
 */
int libmpq_decrypt_blocktable(mpq_archive *mpq_a, unsigned char *pbKey) {
	unsigned int seed1, seed2;
	unsigned int ch;			/* One key character */
	unsigned int *pdwTable = (unsigned int *)(mpq_a->blocktable);
	unsigned int length = mpq_a->header->blocktablesize * 4;

	/* Decrypt it */
    seed1 = libmpq_hash_string(mpq_a, 3, pbKey);
	seed2 = 0xEEEEEEEE;
	while(length-- > 0) {
		seed2 += mpq_a->buf[0x400 + (seed1 & 0xFF)];
		ch     = *pdwTable ^ (seed1 + seed2);
		seed1  = ((~seed1 << 0x15) + 0x11111111) | (seed1 >> 0x0B);
		seed2  = ch + seed2 + (seed2 << 5) + 3;
		*pdwTable++ = ch;
	}
	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This functions tries to get file decryption key. The trick comes from block
 *  positions which are stored at the begin of each compressed file. We know the
 *  file size, that means we know number of blocks that means we know the first
 *  int value in block position. And if we know encrypted and decrypted value,
 *  we can find the decryption key.
 */
int libmpq_detect_fileseed(mpq_archive *mpq_a, unsigned int *block, unsigned int decrypted) {
	unsigned int saveseed1;
	unsigned int temp = *block ^ decrypted;		/* temp = seed1 + seed2 */
	int i = 0;
	temp -= 0xEEEEEEEE;				/* temp = seed1 + mpq_a->buf[0x400 + (seed1 & 0xFF)] */

	for (i = 0; i < 0x100; i++) {			/* Try all 255 possibilities */
		unsigned int seed1;
		unsigned int seed2 = 0xEEEEEEEE;
		unsigned int ch;

		/* Try the first unsigned int's (We exactly know the value) */
		seed1  = temp - mpq_a->buf[0x400 + i];
		seed2 += mpq_a->buf[0x400 + (seed1 & 0xFF)];
		ch     = block[0] ^ (seed1 + seed2);

		if (ch != decrypted) {
			continue;
		}

		/* Add 1 because we are decrypting block positions */
		saveseed1 = seed1 + 1;

		/*
		 *  If OK, continue and test the second value. We don't know exactly the value,
		 *  but we know that the second one has lower 16 bits set to zero
		 *  (no compressed block is larger than 0xFFFF bytes)
		 */
		seed1  = ((~seed1 << 0x15) + 0x11111111) | (seed1 >> 0x0B);
		seed2  = ch + seed2 + (seed2 << 5) + 3;
		seed2 += mpq_a->buf[0x400 + (seed1 & 0xFF)];
		ch     = block[1] ^ (seed1 + seed2);
		if ((ch & 0xFFFF0000) == 0) {
			return saveseed1;
		}
	}
	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This function initialize the decryption buffer
 */
int libmpq_init_buffer(mpq_archive *mpq_a) {
	unsigned int seed   = 0x00100001;
	unsigned int index1 = 0;
	unsigned int index2 = 0;
	int i;

	memset(mpq_a->buf, 0, sizeof(mpq_a->buf));

	/* Initialize the decryption buffer. */
	for (index1 = 0; index1 < 0x100; index1++) {
		for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100) {
			unsigned int temp1, temp2;
			seed  = (seed * 125 + 3) % 0x2AAAAB;
			temp1 = (seed & 0xFFFF) << 0x10;

			seed  = (seed * 125 + 3) % 0x2AAAAB;
			temp2 = (seed & 0xFFFF);

			mpq_a->buf[index2] = (temp1 | temp2);
		}
	}
	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This functions fills the mpq_hash structure with the
 *  hashtable found in the MPQ file. The hashtable will
 *  be decrypted for later use.
 */
int libmpq_read_hashtable(mpq_archive *mpq_a) {
	unsigned int bytes = 0;
	int rb = 0;

	/*
	 *  Allocate memory. Note that the block table should be as large as the
	 *  hash table. (for later file additions)
	 */
	mpq_a->hashtable = (mpq_hash*)malloc(sizeof(mpq_hash) * mpq_a->header->hashtablesize);

	if (!mpq_a->hashtable) {
		return LIBMPQ_EALLOCMEM;
	}

	/* Read the hash table into the buffer */
	bytes = mpq_a->header->hashtablesize * sizeof(mpq_hash);
	lseek(mpq_a->fd, mpq_a->header->hashtablepos, SEEK_SET);
	rb = read(mpq_a->fd, mpq_a->hashtable, bytes);
	if (rb != bytes) {
		return LIBMPQ_EFILE_CORRUPT;
	}

	/* Decrypt hash table and check if it is correctly decrypted */
	mpq_hash *mpq_h_end = mpq_a->hashtable + mpq_a->header->hashtablesize;
	mpq_hash *mpq_h     = NULL;

	libmpq_decrypt_hashtable(mpq_a, (unsigned char*)"(hash table)");

	/* Check hash table if is correctly decrypted */
	for (mpq_h = mpq_a->hashtable; mpq_h < mpq_h_end; mpq_h++) {
		// WoW: patch.MPQ breaks this
		//if (mpq_h->locale != 0xFFFFFFFF && (mpq_h->locale & 0xFFFF0000) != 0) {
		//	return LIBMPQ_EFILE_FORMAT;
		//}

		/* Remember the highest block table entry */
		if (mpq_h->blockindex < LIBMPQ_HASH_ENTRY_DELETED && mpq_h->blockindex > 0) {
			mpq_a->maxblockindex = mpq_h->blockindex;
		}
	}

	return LIBMPQ_TOOLS_SUCCESS;
}

/*
 *  This functions fills the mpq_block structure with the
 *  blocktable found in the MPQ file. The blocktable will
 *  be decrypted for later use.
 *
 *  NOTICE: Some MPQs have decrypted block table, e.g.
 *          cracked Diablo versions.
 */
int libmpq_read_blocktable(mpq_archive *mpq_a) {
	unsigned int bytes = 0;
	int rb = 0;

	/*
	 *  Allocate memory. Note that the block table should be as large as the
	 *  hash table. (for later file additions)
	 */
	mpq_a->blocktable = (mpq_block*)malloc(sizeof(mpq_block) * mpq_a->header->hashtablesize);
	mpq_a->blockbuf   = (unsigned char*)malloc(mpq_a->blocksize);

	if (!mpq_a->blocktable || !mpq_a->blockbuf) {
		return LIBMPQ_EALLOCMEM;
	}

	/* Read the block table into the buffer */
	bytes = mpq_a->header->blocktablesize * sizeof(mpq_block);
	memset(mpq_a->blocktable, 0, mpq_a->header->blocktablesize * sizeof(mpq_block));
	lseek(mpq_a->fd, mpq_a->header->blocktablepos, SEEK_SET);
	rb = read(mpq_a->fd, mpq_a->blocktable, bytes);
	if (rb != bytes) {
		return LIBMPQ_EFILE_CORRUPT;
	}

	/*
	 *  Decrypt block table. Some MPQs don't have encrypted block table,
	 *  e.g. cracked Diablo version. We have to check if block table is
	 *  already decrypted
	 */
	mpq_block *mpq_b_end     = mpq_a->blocktable + mpq_a->maxblockindex + 1;
	mpq_block *mpq_b         = NULL;
	unsigned int archivesize = mpq_a->header->archivesize + mpq_a->mpqpos;

	if (mpq_a->header->offset != mpq_a->blocktable->filepos) {
		libmpq_decrypt_blocktable(mpq_a, (unsigned char*)"(block table)");
	}
	for (mpq_b = mpq_a->blocktable; mpq_b < mpq_b_end; mpq_b++) {
		if (mpq_b->filepos > archivesize || mpq_b->csize > archivesize) {
			if ((mpq_a->flags & LIBMPQ_FLAG_PROTECTED) == 0) {
				return LIBMPQ_EFILE_FORMAT;