Contrib/dmk/combine-dmk.cc at main · doomsdayone/openmsx

◆ main openmsx / Contrib / dmk / combine-dmk.cc

8.4 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw

#include "dmk-common.hh"

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <map>
#include <string>
#include <sys/stat.h>
#include <vector>


class Gaps
{
public:
	explicit Gaps(int totalSize);
	void addInterval(int start, int stop);
	int getLargestGap();
private:
	void addUse2(int start, int stop);

	int totalSize;
	std::vector<int> v;
};

Gaps::Gaps(int totalSize_)
	: totalSize(totalSize_)
{
}

// [start, stop)
void Gaps::addInterval(int start, int stop)
{
	start %= totalSize;
	stop  %= totalSize;

	if (start < stop) {
		addUse2(start, stop);
	} else if (start > stop) {
		addUse2(start, totalSize);
		if (stop != 0) addUse2(0, stop);
	}
}
void Gaps::addUse2(int start, int stop)
{
	assert(start < stop);
	assert(stop <= totalSize);
	v.push_back(2 * start + 0);
	v.push_back(2 * stop  + 1);
}

int Gaps::getLargestGap()
{
	if (v.empty()) return totalSize / 2;

	// sort begin and end point
	std::ranges::sort(v);

	// largest gap found so far (and its start and stop position)
	int maxLen = 0;
	int maxStart = 0;
	int maxStop = 0;

	// last end point is start of first gap
	int start = v.back() / 2;
	if (start == totalSize) start = 0;

	int count = 0;
	for (int i : v) {
		if (i & 1) {
			// interval end point
			--count;
			// no more overlapping intervals -> start of new gap
			if (count == 0) start = i / 2;
		} else {
			// interval begin point
			int stop = i / 2;
			if (count == 0) {
				// found gap: [start, stop)
				int len = stop - start;
				if (len < 0) len += totalSize;
				if (len > maxLen) {
					maxLen   = len;
					maxStart = start;
					maxStop  = stop;
				}
			}
			++count;
		}
	}
	assert(count == 0);

	if (maxLen == 0) return -1;
	if (maxStop < maxStart) maxStop += totalSize;
	int mid = (maxStart + maxStop) / 2;
	return mid % totalSize;
}

///////


static uint8_t readCircular(const std::vector<uint8_t>& buffer, int idx)
{
	auto dmkTrackLen = int(buffer.size());
	return buffer[128 + idx % (dmkTrackLen - 128)];
}

static void verifyDMK(bool b, const char* message)
{
	if (!b) {
		fprintf(stderr, "Invalid input: %s\n", message);
		exit(1);
	}
}

static int analyzeTrack(std::vector<uint8_t>& buffer)
{
	auto dmkTrackLen = int(buffer.size());
	int trackLen = dmkTrackLen - 128;

	Gaps gaps(trackLen);

	for (int i = 0; i < 64; ++i) {
		// Get (and check) pointer into track data
		int dmkIdx = buffer[2 * i + 0] + 256 * buffer[2 * i + 1];
		if (dmkIdx == 0) {
			// end of table reached
			break;
		}
		verifyDMK((dmkIdx & 0xC000) == 0x8000, "double density flag");
		dmkIdx &= ~0xC000; // clear flags
		verifyDMK(dmkIdx >= 128, "IDAM offset too small");
		verifyDMK(dmkIdx < dmkTrackLen, "IDAM offset too large");
		dmkIdx -= 128;

		// read address mark
		int addrIdx = dmkIdx - 3; // might be negative
		uint8_t d0 = readCircular(buffer, addrIdx + 0);
		uint8_t d1 = readCircular(buffer, addrIdx + 1);
		uint8_t d2 = readCircular(buffer, addrIdx + 2);
		uint8_t d3 = readCircular(buffer, addrIdx + 3);
		uint8_t c  = readCircular(buffer, addrIdx + 4);
		uint8_t h  = readCircular(buffer, addrIdx + 5);
		uint8_t r  = readCircular(buffer, addrIdx + 6);
		uint8_t n  = readCircular(buffer, addrIdx + 7);
		uint8_t ch = readCircular(buffer, addrIdx + 8);
		uint8_t cl = readCircular(buffer, addrIdx + 9);

		// address mark CRC
		uint16_t addrCrc = 0xFFFF;
		updateCrc(addrCrc, d0);
		updateCrc(addrCrc, d1);
		updateCrc(addrCrc, d2);
		updateCrc(addrCrc, d3);
		updateCrc(addrCrc, c);
		updateCrc(addrCrc, h);
		updateCrc(addrCrc, r);
		updateCrc(addrCrc, n);
		if (uint16_t onDiskAddrCrc = 256 * ch + cl;
		    onDiskAddrCrc != addrCrc) {
			// only mark address mark as in-use
			gaps.addInterval(addrIdx, addrIdx + 10);
			continue;
		}

		// locate data mark, should be within 43 bytes from end
		// of address mark (according to WD2793 datasheet)
		for (int j = 10; j < 53; ++j) {
			int dataIdx = addrIdx + j;
			uint8_t a0 = readCircular(buffer, dataIdx + 0);
			uint8_t a1 = readCircular(buffer, dataIdx + 1);
			uint8_t a2 = readCircular(buffer, dataIdx + 2);
			uint8_t t  = readCircular(buffer, dataIdx + 3);
			if ((a0 != 0xA1) || (a1 != 0xA1) || (a2 != 0xA1) ||
			    ((t != 0xFB) && (t != 0xF8))) {
				continue;
			}

			// Mark whole region from begin of address mark to end
			// of data as in-use (so including the gap between
			// address and data section).
			int sectorSize = 128 << (n & 3);
			int end = dataIdx + 4 + sectorSize + 2; // header + data + crc
			gaps.addInterval(addrIdx, end);
			break;
		}
		// if (i == 53) --> data mark not found
	}
	return gaps.getLargestGap();
}

int main()
{
	std::vector<std::vector<uint8_t>> data; // buffer all .DAT files

	std::string name = "DMK-tt-s.DAT";
	for (int t = 0; t <= 99; ++t) {
		for (int h = 0; h < 2; ++h) {
			name[4] = char((t / 10) + '0');
			name[5] = char((t % 10) + '0');
			name[7] = char(h + '0');

			FILE_t file(fopen(name.c_str(), "rb"));
			if (!file) {
				if (h == 0) goto done_read;
				fprintf(stderr,
					"Couldn't open file %s, but the "
					"corresponding file for side 0 was "
					"found.\n",
					name.c_str());
				exit(1);
			}

			struct stat st;
			fstat(fileno(file.get()), &st);
			size_t size = st.st_size;
			if (size < 128) {
				fprintf(stderr, "File %s is too small.\n",
				        name.c_str());
				exit(1);
			}

			std::vector<uint8_t> dat(size);
			if (fread(dat.data(), size, 1, file.get()) != 1) {
				fprintf(stderr, "Error reading file %s.\n",
				        name.c_str());
				exit(1);
			}
			data.push_back(dat);
		}
	}
done_read:
	assert((data.size() & 1) == 0);
	auto numTracks = int(data.size() / 2);

	// Check that no .dat files with higher track number are found.
	for (int t = numTracks; t <= 99; ++t) {
		for (int h = 0; h < 2; ++h) {
			name[4] = char((t / 10) + '0');
			name[5] = char((t % 10) + '0');
			name[7] = char(h + '0');

			if (FILE_t file(fopen(name.c_str(), "rb"));
			    !file) continue; // ok, we should not have this file

			std::string name2 = "DMK-tt-0.DAT";
			name2[4] = char((numTracks / 10) + '0');
			name2[5] = char((numTracks % 10) + '0');
			fprintf(stderr,
				"Found file %s, but file %s is missing.\n",
				name.c_str(), name2.c_str());
			exit(1);
		}
	}

	printf("Found .dat files for %d tracks (double sided).\n", numTracks);

	// Create histogram of track lengths.
	std::map<unsigned, unsigned> sizes; // length, count
	for (const auto& d : data) {
		++sizes[d.size()];
	}

	// Search the peak in this histogram (= the track length that occurs
	// most often).
	unsigned maxCount = 0;
	unsigned trackSize = 0;
	for (const auto& [length, count] : sizes) {
		if (count >= maxCount) {
			maxCount = count;
			trackSize = length;
		}
	}

	// Open output file.
	FILE_t file(fopen("out.dmk", "wb+"));
	if (!file) {
		fprintf(stderr, "Couldn't open output file out.dmk.\n");
		exit(1);
	}

	// Write DMK header.
	DmkHeader header;
	memset(&header, 0, sizeof(header));
	header.numTracks = numTracks;
	header.trackLen[0] = trackSize % 256;
	header.trackLen[1] = trackSize / 256;
	if (fwrite(&header, sizeof(header), 1, file.get()) != 1) {
		fprintf(stderr, "Error writing out.dmk.\n");
		exit(1);
	}

	// Process each track.
	for (auto& v : data) {
		// Adjust track size
		while (v.size() != trackSize) {
			// Locate (middle of) largest gap in this track.
			int mid = analyzeTrack(v) + 128;
			if (mid == -1) {
				fprintf(stderr, "Couldn't adjust track length.\n");
				exit(1);
			}
			assert(mid < int(v.size()));

			// We insert or delete one byte at a time. This may not
			// be the most efficient approach (but still more than
			// fast enough, we typically only need to adjust a few
			// bytes anyway). This has the advantage of being very
			// simple: it can easily handle gaps that wrap around
			// from the end to the beginning of the track and it
			// can handle the case that after decreasing a gap with
			// a few bytes another gaps becomes the largest gap.
			int delta;
			if (trackSize > v.size()) {
				delta = 1;
				v.insert(v.begin() + mid, v[mid]);
			} else {
				delta = -1;
				v.erase(v.begin() + mid);
			}

			// After inserting/deleting byte(s), we need to adjust
			// the IDAM table.
			for (int i = 0; i < 64; ++i) {
				int t = v[2 * i + 0] + 256 * v[2 * i + 1];
				if (t == 0) break;
				if ((t & 0x3fff) > mid) t += delta;
				v[2 * i + 0] = t % 256;
				v[2 * i + 1] = t / 256;
			}
		}

		// Write track to DMK file.
		if (fwrite(v.data(), v.size(), 1, file.get()) != 1) {
			fprintf(stderr, "Error writing out.dmk.\n");
			exit(1);
		}
	}

	printf("Successfully wrote out.dmk.\n");
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	#include "dmk-common.hh"
2
3	#include <algorithm>
4	#include <array>
5	#include <cassert>
6	#include <cstdint>
7	#include <cstdlib>
8	#include <cstring>
9	#include <map>
10	#include <string>
11	#include <sys/stat.h>
12	#include <vector>
13
14
15	class Gaps
16	{
17	public:
18	explicit Gaps(int totalSize);
19	void addInterval(int start, int stop);
20	int getLargestGap();
21	private:
22	void addUse2(int start, int stop);
23
24	int totalSize;
25	std::vector<int> v;
26	};
27
28	Gaps::Gaps(int totalSize_)
29	: totalSize(totalSize_)
30	{
31	}
32
33	// [start, stop)
34	void Gaps::addInterval(int start, int stop)
35	{
36	start %= totalSize;
37	stop %= totalSize;
38
39	if (start < stop) {
40	addUse2(start, stop);
41	} else if (start > stop) {
42	addUse2(start, totalSize);
43	if (stop != 0) addUse2(0, stop);
44	}
45	}
46	void Gaps::addUse2(int start, int stop)
47	{
48	assert(start < stop);
49	assert(stop <= totalSize);
50	v.push_back(2 * start + 0);
51	v.push_back(2 * stop + 1);
52	}
53
54	int Gaps::getLargestGap()
55	{
56	if (v.empty()) return totalSize / 2;
57
58	// sort begin and end point
59	std::ranges::sort(v);
60
61	// largest gap found so far (and its start and stop position)
62	int maxLen = 0;
63	int maxStart = 0;
64	int maxStop = 0;
65
66	// last end point is start of first gap
67	int start = v.back() / 2;
68	if (start == totalSize) start = 0;
69
70	int count = 0;
71	for (int i : v) {
72	if (i & 1) {
73	// interval end point
74	--count;
75	// no more overlapping intervals -> start of new gap
76	if (count == 0) start = i / 2;
77	} else {
78	// interval begin point
79	int stop = i / 2;
80	if (count == 0) {
81	// found gap: [start, stop)
82	int len = stop - start;
83	if (len < 0) len += totalSize;
84	if (len > maxLen) {
85	maxLen = len;
86	maxStart = start;
87	maxStop = stop;
88	}
89	}
90	++count;
91	}
92	}
93	assert(count == 0);
94
95	if (maxLen == 0) return -1;
96	if (maxStop < maxStart) maxStop += totalSize;
97	int mid = (maxStart + maxStop) / 2;
98	return mid % totalSize;
99	}
100
101	///////
102
103
104	static uint8_t readCircular(const std::vector<uint8_t>& buffer, int idx)
105	{
106	auto dmkTrackLen = int(buffer.size());
107	return buffer[128 + idx % (dmkTrackLen - 128)];
108	}
109
110	static void verifyDMK(bool b, const char* message)
111	{
112	if (!b) {
113	fprintf(stderr, "Invalid input: %s\n", message);
114	exit(1);
115	}
116	}
117
118	static int analyzeTrack(std::vector<uint8_t>& buffer)
119	{
120	auto dmkTrackLen = int(buffer.size());
121	int trackLen = dmkTrackLen - 128;
122
123	Gaps gaps(trackLen);
124
125	for (int i = 0; i < 64; ++i) {
126	// Get (and check) pointer into track data
127	int dmkIdx = buffer[2 * i + 0] + 256 * buffer[2 * i + 1];
128	if (dmkIdx == 0) {
129	// end of table reached
130	break;
131	}
132	verifyDMK((dmkIdx & 0xC000) == 0x8000, "double density flag");
133	dmkIdx &= ~0xC000; // clear flags
134	verifyDMK(dmkIdx >= 128, "IDAM offset too small");
135	verifyDMK(dmkIdx < dmkTrackLen, "IDAM offset too large");
136	dmkIdx -= 128;
137
138	// read address mark
139	int addrIdx = dmkIdx - 3; // might be negative
140	uint8_t d0 = readCircular(buffer, addrIdx + 0);
141	uint8_t d1 = readCircular(buffer, addrIdx + 1);
142	uint8_t d2 = readCircular(buffer, addrIdx + 2);
143	uint8_t d3 = readCircular(buffer, addrIdx + 3);
144	uint8_t c = readCircular(buffer, addrIdx + 4);
145	uint8_t h = readCircular(buffer, addrIdx + 5);
146	uint8_t r = readCircular(buffer, addrIdx + 6);
147	uint8_t n = readCircular(buffer, addrIdx + 7);
148	uint8_t ch = readCircular(buffer, addrIdx + 8);
149	uint8_t cl = readCircular(buffer, addrIdx + 9);
150
151	// address mark CRC
152	uint16_t addrCrc = 0xFFFF;
153	updateCrc(addrCrc, d0);
154	updateCrc(addrCrc, d1);
155	updateCrc(addrCrc, d2);
156	updateCrc(addrCrc, d3);
157	updateCrc(addrCrc, c);
158	updateCrc(addrCrc, h);
159	updateCrc(addrCrc, r);
160	updateCrc(addrCrc, n);
161	if (uint16_t onDiskAddrCrc = 256 * ch + cl;
162	onDiskAddrCrc != addrCrc) {
163	// only mark address mark as in-use
164	gaps.addInterval(addrIdx, addrIdx + 10);
165	continue;
166	}
167
168	// locate data mark, should be within 43 bytes from end
169	// of address mark (according to WD2793 datasheet)
170	for (int j = 10; j < 53; ++j) {
171	int dataIdx = addrIdx + j;
172	uint8_t a0 = readCircular(buffer, dataIdx + 0);
173	uint8_t a1 = readCircular(buffer, dataIdx + 1);
174	uint8_t a2 = readCircular(buffer, dataIdx + 2);
175	uint8_t t = readCircular(buffer, dataIdx + 3);
176	if ((a0 != 0xA1) \|\| (a1 != 0xA1) \|\| (a2 != 0xA1) \|\|
177	((t != 0xFB) && (t != 0xF8))) {
178	continue;
179	}
180
181	// Mark whole region from begin of address mark to end
182	// of data as in-use (so including the gap between
183	// address and data section).
184	int sectorSize = 128 << (n & 3);
185	int end = dataIdx + 4 + sectorSize + 2; // header + data + crc
186	gaps.addInterval(addrIdx, end);
187	break;
188	}
189	// if (i == 53) --> data mark not found
190	}
191	return gaps.getLargestGap();
192	}
193
194	int main()
195	{
196	std::vector<std::vector<uint8_t>> data; // buffer all .DAT files
197
198	std::string name = "DMK-tt-s.DAT";
199	for (int t = 0; t <= 99; ++t) {
200	for (int h = 0; h < 2; ++h) {
201	name[4] = char((t / 10) + '0');
202	name[5] = char((t % 10) + '0');
203	name[7] = char(h + '0');
204
205	FILE_t file(fopen(name.c_str(), "rb"));
206	if (!file) {
207	if (h == 0) goto done_read;
208	fprintf(stderr,
209	"Couldn't open file %s, but the "
210	"corresponding file for side 0 was "
211	"found.\n",
212	name.c_str());
213	exit(1);
214	}
215
216	struct stat st;
217	fstat(fileno(file.get()), &st);
218	size_t size = st.st_size;
219	if (size < 128) {
220	fprintf(stderr, "File %s is too small.\n",
221	name.c_str());
222	exit(1);
223	}
224
225	std::vector<uint8_t> dat(size);
226	if (fread(dat.data(), size, 1, file.get()) != 1) {
227	fprintf(stderr, "Error reading file %s.\n",
228	name.c_str());
229	exit(1);
230	}
231	data.push_back(dat);
232	}
233	}
234	done_read:
235	assert((data.size() & 1) == 0);
236	auto numTracks = int(data.size() / 2);
237
238	// Check that no .dat files with higher track number are found.
239	for (int t = numTracks; t <= 99; ++t) {
240	for (int h = 0; h < 2; ++h) {
241	name[4] = char((t / 10) + '0');
242	name[5] = char((t % 10) + '0');
243	name[7] = char(h + '0');
244
245	if (FILE_t file(fopen(name.c_str(), "rb"));
246	!file) continue; // ok, we should not have this file
247
248	std::string name2 = "DMK-tt-0.DAT";
249	name2[4] = char((numTracks / 10) + '0');
250	name2[5] = char((numTracks % 10) + '0');
251	fprintf(stderr,
252	"Found file %s, but file %s is missing.\n",
253	name.c_str(), name2.c_str());
254	exit(1);
255	}
256	}
257
258	printf("Found .dat files for %d tracks (double sided).\n", numTracks);
259
260	// Create histogram of track lengths.
261	std::map<unsigned, unsigned> sizes; // length, count
262	for (const auto& d : data) {
263	++sizes[d.size()];
264	}
265
266	// Search the peak in this histogram (= the track length that occurs
267	// most often).
268	unsigned maxCount = 0;
269	unsigned trackSize = 0;
270	for (const auto& [length, count] : sizes) {
271	if (count >= maxCount) {
272	maxCount = count;
273	trackSize = length;
274	}
275	}
276
277	// Open output file.
278	FILE_t file(fopen("out.dmk", "wb+"));
279	if (!file) {
280	fprintf(stderr, "Couldn't open output file out.dmk.\n");
281	exit(1);
282	}
283
284	// Write DMK header.
285	DmkHeader header;
286	memset(&header, 0, sizeof(header));
287	header.numTracks = numTracks;
288	header.trackLen[0] = trackSize % 256;
289	header.trackLen[1] = trackSize / 256;
290	if (fwrite(&header, sizeof(header), 1, file.get()) != 1) {
291	fprintf(stderr, "Error writing out.dmk.\n");
292	exit(1);
293	}
294
295	// Process each track.
296	for (auto& v : data) {
297	// Adjust track size
298	while (v.size() != trackSize) {
299	// Locate (middle of) largest gap in this track.
300	int mid = analyzeTrack(v) + 128;
301	if (mid == -1) {
302	fprintf(stderr, "Couldn't adjust track length.\n");
303	exit(1);
304	}
305	assert(mid < int(v.size()));
306
307	// We insert or delete one byte at a time. This may not
308	// be the most efficient approach (but still more than
309	// fast enough, we typically only need to adjust a few
310	// bytes anyway). This has the advantage of being very
311	// simple: it can easily handle gaps that wrap around
312	// from the end to the beginning of the track and it
313	// can handle the case that after decreasing a gap with
314	// a few bytes another gaps becomes the largest gap.
315	int delta;
316	if (trackSize > v.size()) {
317	delta = 1;
318	v.insert(v.begin() + mid, v[mid]);
319	} else {
320	delta = -1;
321	v.erase(v.begin() + mid);
322	}
323
324	// After inserting/deleting byte(s), we need to adjust
325	// the IDAM table.
326	for (int i = 0; i < 64; ++i) {
327	int t = v[2 * i + 0] + 256 * v[2 * i + 1];
328	if (t == 0) break;
329	if ((t & 0x3fff) > mid) t += delta;
330	v[2 * i + 0] = t % 256;
331	v[2 * i + 1] = t / 256;
332	}
333	}
334
335	// Write track to DMK file.
336	if (fwrite(v.data(), v.size(), 1, file.get()) != 1) {
337	fprintf(stderr, "Error writing out.dmk.\n");
338	exit(1);
339	}
340	}
341
342	printf("Successfully wrote out.dmk.\n");
343	}

Keyboard