/*
 * Copyright 2012, Jérôme Duval, korli@users.berlios.de.
 * Copyright 2003, Tyler Dauwalder, tyler@dauwalder.net.
 * Distributed under the terms of the MIT License.
 */


#include "Recognition.h"

#include "UdfString.h"
#include "MemoryChunk.h"
#include "Utils.h"

#include <string.h>


//------------------------------------------------------------------------------
// forward declarations
//------------------------------------------------------------------------------

static status_t
walk_volume_recognition_sequence(int device, off_t offset, uint32 blockSize,
	uint32 blockShift);

static status_t
walk_anchor_volume_descriptor_sequences(int device, off_t offset, off_t length,
	uint32 blockSize, uint32 blockShift,
	primary_volume_descriptor &primaryVolumeDescriptor,
	logical_volume_descriptor &logicalVolumeDescriptor,
	partition_descriptor partitionDescriptors[],
	uint8 &partitionDescriptorCount);

static status_t
walk_volume_descriptor_sequence(extent_address descriptorSequence, int device,
	uint32 blockSize, uint32 blockShift,
	primary_volume_descriptor &primaryVolumeDescriptor,
	logical_volume_descriptor &logicalVolumeDescriptor,
	partition_descriptor partitionDescriptors[],
	uint8 &partitionDescriptorCount);

static status_t
walk_integrity_sequence(int device, uint32 blockSize, uint32 blockShift,
	extent_address descriptorSequence, uint32 sequenceNumber = 0);

//------------------------------------------------------------------------------
// externally visible functions
//------------------------------------------------------------------------------


status_t
udf_recognize(int device, off_t offset, off_t length, uint32 blockSize,
	uint32 &blockShift, primary_volume_descriptor &primaryVolumeDescriptor,
	logical_volume_descriptor &logicalVolumeDescriptor,
	partition_descriptor partitionDescriptors[],
	uint8 &partitionDescriptorCount)
{
	TRACE(("udf_recognize: device: = %d, offset = %" B_PRIdOFF ", length = %"
		B_PRIdOFF ", blockSize = %" B_PRIu32 "\n", device, offset, length,
		blockSize));
	// Check the block size
	status_t status = get_block_shift(blockSize, blockShift);
	if (status != B_OK) {
		TRACE_ERROR(("\nudf_recognize: Block size must be a positive power of "
			"two! (blockSize = %" B_PRIu32 ")\n", blockSize));
		return status;
	}
	TRACE(("blockShift: %" B_PRIu32 "\n", blockShift));

	// Check for a valid volume recognition sequence
	status = walk_volume_recognition_sequence(device, offset, blockSize,
		blockShift);
	if (status != B_OK) {
		TRACE(("udf_recognize: Invalid sequence. status = %" B_PRId32
			"\n", status));
		return status;
	}
	// Now hunt down a volume descriptor sequence from one of
	// the anchor volume pointers (if there are any).
	status = walk_anchor_volume_descriptor_sequences(device, offset, length,
		blockSize, blockShift, primaryVolumeDescriptor,
		logicalVolumeDescriptor, partitionDescriptors,
		partitionDescriptorCount);
	if (status != B_OK) {
		TRACE_ERROR(("udf_recognize: cannot find volume descriptor. status = %"
			B_PRId32 "\n", status));
		return status;
	}
	// Now walk the integrity sequence and make sure the last integrity
	// descriptor is a closed descriptor
	status = walk_integrity_sequence(device, blockSize, blockShift,
		logicalVolumeDescriptor.integrity_sequence_extent());
	if (status != B_OK) {
		TRACE_ERROR(("udf_recognize: last integrity descriptor not closed. "
			"status = %" B_PRId32 "\n", status));
		return status;
	}

	return B_OK;
}

//------------------------------------------------------------------------------
// local functions
//------------------------------------------------------------------------------

static
status_t
walk_volume_recognition_sequence(int device, off_t offset, uint32 blockSize,
	uint32 blockShift)
{
	TRACE(("walk_volume_recognition_sequence: device = %d, offset = %"
		B_PRIdOFF ", blockSize = %" B_PRIu32 ", blockShift = %" B_PRIu32 "\n",
		device, offset, blockSize, blockShift));

	// vrs starts at block 16. Each volume structure descriptor (vsd)
	// should be one block long. We're expecting to find 0 or more iso9660
	// vsd's followed by some ECMA-167 vsd's.
	MemoryChunk chunk(blockSize);
	if (chunk.InitCheck() != B_OK) {
		TRACE_ERROR(("walk_volume_recognition_sequence: Failed to construct "
			"MemoryChunk\n"));
		return chunk.InitCheck();
	}

	bool foundExtended = false;
	bool foundECMA167 = false;
	bool foundECMA168 = false;
	for (uint32 block = 16; true; block++) {
		off_t address = (offset + block) << blockShift;
		TRACE(("walk_volume_recognition_sequence: block = %" B_PRIu32 ", "
			"address = %" B_PRIdOFF ", ", block, address));
		ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
		if (bytesRead == (ssize_t)blockSize) {
			volume_structure_descriptor_header* descriptor
				= (volume_structure_descriptor_header *)(chunk.Data());
			if (descriptor->id_matches(kVSDID_ISO)) {
				TRACE(("found ISO9660 descriptor\n"));
			} else if (descriptor->id_matches(kVSDID_BEA)) {
				TRACE(("found BEA descriptor\n"));
				foundExtended = true;
			} else if (descriptor->id_matches(kVSDID_TEA)) {
				TRACE(("found TEA descriptor\n"));
				foundExtended = true;
			} else if (descriptor->id_matches(kVSDID_ECMA167_2)) {
				TRACE(("found ECMA-167 rev 2 descriptor\n"));
				foundECMA167 = true;
			} else if (descriptor->id_matches(kVSDID_ECMA167_3)) {
				TRACE(("found ECMA-167 rev 3 descriptor\n"));
				foundECMA167 = true;
			} else if (descriptor->id_matches(kVSDID_BOOT)) {
				TRACE(("found boot descriptor\n"));
			} else if (descriptor->id_matches(kVSDID_ECMA168)) {
				TRACE(("found ECMA-168 descriptor\n"));
				foundECMA168 = true;
			} else {
				TRACE(("found invalid descriptor, id = `%.5s'\n", descriptor->id));
				break;
			}
		} else {
			TRACE(("read_pos(pos:%" B_PRIdOFF ", len:%" B_PRIu32 ") "
				"failed with: 0x%lx\n", address, blockSize, bytesRead));
			break;
		}
	}

	// If we find an ECMA-167 descriptor, OR if we find a beginning
	// or terminating extended area descriptor with NO ECMA-168
	// descriptors, we return B_OK to signal that we should go
	// looking for valid anchors.
	return foundECMA167 || (foundExtended && !foundECMA168) ? B_OK : B_ERROR;
}


static status_t
walk_anchor_volume_descriptor_sequences(int device, off_t offset, off_t length,
	uint32 blockSize, uint32 blockShift,
	primary_volume_descriptor &primaryVolumeDescriptor,
	logical_volume_descriptor &logicalVolumeDescriptor,
	partition_descriptor partitionDescriptors[],
	uint8 &partitionDescriptorCount)
{
	DEBUG_INIT(NULL);
	const uint8 avds_location_count = 4;
	const off_t avds_locations[avds_location_count]
		= { 256, length-1-256, length-1, 512, };
	bool found_vds = false;
	for (int32 i = 0; i < avds_location_count; i++) {
		off_t block = avds_locations[i];
		off_t address = (offset + block) << blockShift;
		MemoryChunk chunk(blockSize);
		anchor_volume_descriptor *anchor = NULL;

		status_t anchorErr = chunk.InitCheck();
		if (!anchorErr) {
			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
			anchorErr = bytesRead == (ssize_t)blockSize ? B_OK : B_IO_ERROR;
			if (anchorErr) {
				PRINT(("block %" B_PRIdOFF ": read_pos(pos:%" B_PRIdOFF ", "
						"len:%" PRIu32 ") failed with error 0x%lx\n",
					block, address, blockSize, bytesRead));
			}
		}
		if (!anchorErr) {
			anchor = reinterpret_cast<anchor_volume_descriptor*>(chunk.Data());
			anchorErr = anchor->tag().init_check(block + offset);
			if (anchorErr) {
				PRINT(("block %" B_PRIdOFF ": invalid anchor\n", block));
			} else {
				PRINT(("block %" B_PRIdOFF ": valid anchor\n", block));
			}
		}
		if (!anchorErr) {
			PRINT(("block %" B_PRIdOFF ": anchor:\n", block));
			PDUMP(anchor);
			// Found an avds, so try the main sequence first, then
			// the reserve sequence if the main one fails.
			anchorErr = walk_volume_descriptor_sequence(anchor->main_vds(),
				device, blockSize, blockShift, primaryVolumeDescriptor,
				logicalVolumeDescriptor, partitionDescriptors,
				partitionDescriptorCount);

			if (anchorErr)
				anchorErr = walk_volume_descriptor_sequence(anchor->reserve_vds(),
					device,	blockSize, blockShift, primaryVolumeDescriptor,
					logicalVolumeDescriptor, partitionDescriptors,
					partitionDescriptorCount);
		}
		if (!anchorErr) {
			PRINT(("block %" B_PRIdOFF ": found valid vds\n",
				avds_locations[i]));
			found_vds = true;
			break;
		} else {
			// Both failed, so loop around and try another avds
			PRINT(("block %" B_PRIdOFF ": vds search failed\n",
				avds_locations[i]));
		}
	}
	status_t error = found_vds ? B_OK : B_ERROR;
	RETURN(error);
}

static status_t
walk_tagid_partition_descriptor(descriptor_tag  *tag, off_t block,
	uint8& uniquePartitions, partition_descriptor* partitionDescriptors)
{
	DEBUG_INIT(NULL);

	status_t error = B_OK;
	partition_descriptor *partition =
		reinterpret_cast<partition_descriptor*>(tag);
	PDUMP(partition);
	if (partition->tag().init_check(block) == B_OK) {
		// Check for a previously discovered partition descriptor with
		// the same number as this partition. If found, keep the one with
		// the higher vds number.
		bool foundDuplicate = false;
		int num;
		for (num = 0; num < uniquePartitions; num++) {
			if (partitionDescriptors[num].partition_number()
				== partition->partition_number()) {
				foundDuplicate = true;
				if (partitionDescriptors[num].vds_number()
					< partition->vds_number()) {
					partitionDescriptors[num] = *partition;
					PRINT(("Replacing previous partition #%d "
						"(vds_number: %" B_PRIu32 ") with new partition #%d "
						"(vds_number: %" B_PRIu32 ")\n",
						partitionDescriptors[num].partition_number(),
						partitionDescriptors[num].vds_number(),
						partition->partition_number(),
						partition->vds_number()));
				}
				break;
			}
		}
		// If we didn't find a duplicate, see if we have any open descriptor
		// spaces left.
		if (!foundDuplicate) {
			if (num < kMaxPartitionDescriptors) {
			// At least one more partition descriptor allowed
				partitionDescriptors[num] = *partition;
				uniquePartitions++;
				PRINT(("Adding partition #%d (vds_number: %" B_PRIu32 ")\n",
					partition->partition_number(),
					partition->vds_number()));
			} else {
				// We've found more than kMaxPartitionDescriptor uniquely-
				// numbered partitions. So, search through the partitions
				// we already have again, this time just looking for a
				// partition with a lower vds number. If we find one,
				// replace it with this one. If we don't, scream bloody
				// murder.
				bool foundReplacement = false;
				for (int j = 0; j < uniquePartitions; j++) {
					if (partitionDescriptors[j].vds_number()
						< partition->vds_number()) {
						foundReplacement = true;
						partitionDescriptors[j] = *partition;
						PRINT(("Replacing partition #%d "
							"(vds_number: %" B_PRIu32 ") "
							"with partition #%d "
							"(vds_number: %" B_PRIu32 ")\n",
							partitionDescriptors[j].partition_number(),
							partitionDescriptors[j].vds_number(),
							partition->partition_number(),
							partition->vds_number()));
							break;
					}
				}
				if (!foundReplacement) {
					PRINT(("Found more than kMaxPartitionDescriptors == %d "
					"unique partition descriptors!\n",
					kMaxPartitionDescriptors));
						error = B_BAD_VALUE;
				}
			}
		}
	}

	RETURN(error);
}

static
status_t
walk_volume_descriptor_sequence(extent_address descriptorSequence,
	int device, uint32 blockSize, uint32 blockShift,
	primary_volume_descriptor &primaryVolumeDescriptor,
	logical_volume_descriptor &logicalVolumeDescriptor,
	partition_descriptor partitionDescriptors[],
	uint8 &partitionDescriptorCount)
{
	DEBUG_INIT_ETC(NULL, ("descriptorSequence.loc:%" PRIu32 ", "
			"descriptorSequence.len:%" PRIu32,
		descriptorSequence.location(), descriptorSequence.length()));
	uint32 count = descriptorSequence.length() >> blockShift;

	bool foundLogicalVolumeDescriptor = false;
	bool foundUnallocatedSpaceDescriptor = false;
	bool foundUdfImplementationUseDescriptor = false;
	uint8 uniquePartitions = 0;
	status_t error = B_OK;

	for (uint32 i = 0; i < count; i++) {
		off_t block = descriptorSequence.location()+i;
		off_t address = block << blockShift;
		MemoryChunk chunk(blockSize);
		descriptor_tag  *tag = NULL;

		PRINT(("descriptor #%" PRIu32 " (block %" B_PRIdOFF "):\n", i, block));

		status_t loopError = chunk.InitCheck();
		if (!loopError) {
			ssize_t bytesRead = read_pos(device, address, chunk.Data(),
				blockSize);
			loopError = bytesRead == (ssize_t)blockSize ? B_OK : B_IO_ERROR;
			if (loopError) {
				PRINT(("block %" B_PRIdOFF ": read_pos(pos:%" B_PRIdOFF ", "
						"len:%" B_PRIu32 ") failed with error 0x%lx\n",
					block, address, blockSize, bytesRead));
			}
		}
		if (!loopError) {
			tag = reinterpret_cast<descriptor_tag *>(chunk.Data());
			loopError = tag->init_check(block);
		}
		if (!loopError) {
			// Now decide what type of descriptor we have
			switch (tag->id()) {
				case TAGID_UNDEFINED:
					break;

				case TAGID_PRIMARY_VOLUME_DESCRIPTOR:
				{
					primary_volume_descriptor *primary =
						reinterpret_cast<primary_volume_descriptor*>(tag);
					PDUMP(primary);
					primaryVolumeDescriptor = *primary;
					break;
				}

				case TAGID_ANCHOR_VOLUME_DESCRIPTOR_POINTER:
					break;

				case TAGID_VOLUME_DESCRIPTOR_POINTER:
					break;

				case TAGID_IMPLEMENTATION_USE_VOLUME_DESCRIPTOR:
				{
					implementation_use_descriptor *impUse =
						reinterpret_cast<implementation_use_descriptor*>(tag);
					PDUMP(impUse);
					// Check for a matching implementation id string
					//  (note that the revision version is not checked)
					if (impUse->tag().init_check(block) == B_OK
						&& impUse->implementation_id().matches(
						kLogicalVolumeInfoId201)) {
								foundUdfImplementationUseDescriptor = true;
					}
					break;
				}

				case TAGID_PARTITION_DESCRIPTOR:
				{
					error = walk_tagid_partition_descriptor(
						tag, block, uniquePartitions, partitionDescriptors);
					break;
				}

				case TAGID_LOGICAL_VOLUME_DESCRIPTOR:
				{
					logical_volume_descriptor *logical =
						reinterpret_cast<logical_volume_descriptor*>(tag);
					PDUMP(logical);
					if (foundLogicalVolumeDescriptor) {
						// Keep the vd with the highest vds_number
						if (logicalVolumeDescriptor.vds_number()
							< logical->vds_number()) {
								logicalVolumeDescriptor = *logical;
						}
					} else {
						logicalVolumeDescriptor = *logical;
						foundLogicalVolumeDescriptor = true;
					}
					break;
				}

				case TAGID_UNALLOCATED_SPACE_DESCRIPTOR:
				{
					unallocated_space_descriptor *unallocated =
						reinterpret_cast<unallocated_space_descriptor*>(tag);
					PDUMP(unallocated);
					foundUnallocatedSpaceDescriptor = true;
					(void)unallocated;	// kill the warning
					break;
				}

				case TAGID_TERMINATING_DESCRIPTOR:
				{
					terminating_descriptor *terminating =
						reinterpret_cast<terminating_descriptor*>(tag);
					PDUMP(terminating);
					(void)terminating;	// kill the warning
					break;
				}

				case TAGID_LOGICAL_VOLUME_INTEGRITY_DESCRIPTOR:
					// Not found in this descriptor sequence
					break;

				default:
					break;

			}
		}
	}

	PRINT(("found %d unique partition%s\n", uniquePartitions,
		(uniquePartitions == 1 ? "" : "s")));

	if (!error && !foundUdfImplementationUseDescriptor) {
		INFORM(("WARNING: no valid udf implementation use descriptor found\n"));
	}
	if (!error)
		error = foundLogicalVolumeDescriptor
			&& foundUnallocatedSpaceDescriptor
			? B_OK : B_ERROR;
	if (!error)
		error = uniquePartitions >= 1 ? B_OK : B_ERROR;
	if (!error)
		partitionDescriptorCount = uniquePartitions;

	RETURN(error);
}

/*! \brief Walks the integrity sequence in the extent given by \a descriptorSequence.

	\return
	- \c B_OK: Success. the sequence was terminated by a valid, closed
		integrity descriptor.
	- \c B_ENTRY_NOT_FOUND: The sequence was empty.
	- (other error code): The sequence was non-empty and did not end in a valid,
                          closed integrity descriptor.
*/
static status_t
walk_integrity_sequence(int device, uint32 blockSize, uint32 blockShift,
                        extent_address descriptorSequence, uint32 sequenceNumber)
{
	DEBUG_INIT_ETC(NULL,
		("descriptorSequence.loc:%" B_PRIu32 ", "
		"descriptorSequence.len:%" B_PRIu32 ,
		descriptorSequence.location(), descriptorSequence.length()));
	uint32 count = descriptorSequence.length() >> blockShift;

	bool lastDescriptorWasClosed = false;
	uint16 highestMinimumUDFReadRevision = 0x0000;
	status_t error = count > 0 ? B_OK : B_ENTRY_NOT_FOUND;
	for (uint32 i = 0; error == B_OK && i < count; i++) {
		off_t block = descriptorSequence.location()+i;
		off_t address = block << blockShift;
		MemoryChunk chunk(blockSize);
		descriptor_tag *tag = NULL;

		PRINT(("integrity descriptor #%" B_PRIu32 ":%" B_PRIu32
			" (block %" B_PRIdOFF "):\n",
			sequenceNumber, i, block));

		status_t loopError = chunk.InitCheck();
		if (!loopError) {
			ssize_t bytesRead = read_pos(device, address, chunk.Data(), blockSize);
			loopError = check_size_error(bytesRead, blockSize);
			if (loopError) {
				PRINT(("block %" B_PRIdOFF": read_pos(pos:%" B_PRIdOFF
					", len:%" B_PRIu32 ") failed with error 0x%lx\n",
					block, address, blockSize, bytesRead));
			}
		}
		if (!loopError) {
			tag = reinterpret_cast<descriptor_tag *>(chunk.Data());
			loopError = tag->init_check(block);
		}
		if (!loopError) {
			// Check the descriptor type and see if it's closed.
			loopError = tag->id() == TAGID_LOGICAL_VOLUME_INTEGRITY_DESCRIPTOR
				? B_OK : B_BAD_DATA;
			if (!loopError) {
				logical_volume_integrity_descriptor *descriptor =
					reinterpret_cast<logical_volume_integrity_descriptor*>(chunk.Data());
				PDUMP(descriptor);
				lastDescriptorWasClosed = descriptor->integrity_type() == INTEGRITY_CLOSED;
				if (lastDescriptorWasClosed) {
					uint16 minimumRevision = descriptor->minimum_udf_read_revision();
					if (minimumRevision > highestMinimumUDFReadRevision) {
						highestMinimumUDFReadRevision = minimumRevision;
					} else if (minimumRevision < highestMinimumUDFReadRevision) {
						INFORM(("WARNING: found decreasing minimum udf read revision in integrity "
							"sequence (last highest: 0x%04x, current: 0x%04x); using higher "
							"revision.\n", highestMinimumUDFReadRevision, minimumRevision));
					}
				}

				// Check a continuation extent if necessary. Note that this effectively
				// ends our search through this extent
				extent_address &next = descriptor->next_integrity_extent();
				if (next.length() > 0) {
					status_t nextError = walk_integrity_sequence(device, blockSize, blockShift,
						next, sequenceNumber+1);
					if (nextError && nextError != B_ENTRY_NOT_FOUND) {
						// Continuation proved invalid
						error = nextError;
						break;
					} else {
						// Either the continuation was valid or empty; either way,
						// we're done searching.
						break;
					}
				}
			} else {
				PDUMP(tag);
			}
		}
		// If we hit an error on the first item, consider the extent empty,
		// otherwise just break out of the loop and assume part of the
		// extent is unrecorded
		if (loopError) {
			if (i == 0)
				error = B_ENTRY_NOT_FOUND;
			else
				break;
		}
	}
	if (!error)
		error = lastDescriptorWasClosed ? B_OK : B_BAD_DATA;
	if (error == B_OK
		&& highestMinimumUDFReadRevision > UDF_MAX_READ_REVISION) {
		error = B_ERROR;
		FATAL(("found udf revision 0x%x more than max 0x%x\n",
			highestMinimumUDFReadRevision, UDF_MAX_READ_REVISION));
	}
	RETURN(error);
}