From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- semestr-4/sieci/cwiczenia1/c1.pdf | Bin 0 -> 164919 bytes semestr-4/sieci/cwiczenia1/cw1.pdf | Bin 0 -> 1647345 bytes semestr-4/sieci/cwiczenia1/out.pdf | Bin 0 -> 1613073 bytes semestr-4/sieci/cwiczenia1/rozw.pdf | Bin 0 -> 26846 bytes semestr-4/sieci/cwiczenia2/.cpp.cpp | 41 ++++ semestr-4/sieci/cwiczenia2/c2.pdf | Bin 0 -> 179367 bytes semestr-4/sieci/pracownia1/makefile | 19 ++ semestr-4/sieci/pracownia1/p1.pdf | Bin 0 -> 79285 bytes semestr-4/sieci/pracownia1/traceroute.c | 240 ++++++++++++++++++ .../sieci/pracownia2/franciszek_malinka.tar.xz | Bin 0 -> 6012 bytes .../sieci/pracownia2/franciszek_malinka/config.h | 15 ++ .../pracownia2/franciszek_malinka/dist_vector.c | 114 +++++++++ .../pracownia2/franciszek_malinka/dist_vector.h | 36 +++ .../pracownia2/franciszek_malinka/linked_list.c | 79 ++++++ .../pracownia2/franciszek_malinka/linked_list.h | 42 ++++ .../sieci/pracownia2/franciszek_malinka/makefile | 34 +++ .../pracownia2/franciszek_malinka/network_addr.c | 65 +++++ .../pracownia2/franciszek_malinka/network_addr.h | 28 +++ .../sieci/pracownia2/franciszek_malinka/router.c | 60 +++++ .../sieci/pracownia2/franciszek_malinka/test.c | 52 ++++ .../sieci/pracownia2/franciszek_malinka/utils.c | 208 ++++++++++++++++ .../sieci/pracownia2/franciszek_malinka/utils.h | 52 ++++ semestr-4/sieci/pracownia2/p2.pdf | Bin 0 -> 98190 bytes semestr-4/sieci/pracownia2/router/config.h | 15 ++ semestr-4/sieci/pracownia2/router/dist_vector.c | 114 +++++++++ semestr-4/sieci/pracownia2/router/dist_vector.h | 36 +++ semestr-4/sieci/pracownia2/router/linked_list.c | 79 ++++++ semestr-4/sieci/pracownia2/router/linked_list.h | 42 ++++ semestr-4/sieci/pracownia2/router/makefile | 34 +++ semestr-4/sieci/pracownia2/router/network_addr.c | 65 +++++ semestr-4/sieci/pracownia2/router/network_addr.h | 28 +++ semestr-4/sieci/pracownia2/router/router.c | 60 +++++ semestr-4/sieci/pracownia2/router/test.c | 52 ++++ semestr-4/sieci/pracownia2/router/utils.c | 208 ++++++++++++++++ semestr-4/sieci/pracownia2/router/utils.h | 52 ++++ semestr-4/sieci/pracownia2/udp_client.c | 41 ++++ semestr-4/sieci/pracownia2/udp_server.c | 59 +++++ semestr-4/sieci/pracownia3/4pkt/config.h | 7 + semestr-4/sieci/pracownia3/4pkt/transport.c | 152 ++++++++++++ semestr-4/sieci/pracownia3/config.h | 10 + .../sieci/pracownia3/franciszek_malinka.tar.xz | Bin 0 -> 2744 bytes .../sieci/pracownia3/franciszek_malinka/config.h | 10 + .../pracownia3/franciszek_malinka/transport.c | 149 ++++++++++++ .../sieci/pracownia3/franciszek_malinka/utils.c | 58 +++++ .../sieci/pracownia3/franciszek_malinka/utils.h | 18 ++ .../sieci/pracownia3/franciszek_malinka/window.c | 42 ++++ .../sieci/pracownia3/franciszek_malinka/window.h | 24 ++ semestr-4/sieci/pracownia3/p3.pdf | Bin 0 -> 95110 bytes semestr-4/sieci/pracownia3/transport.c | 149 ++++++++++++ semestr-4/sieci/pracownia3/utils.c | 58 +++++ semestr-4/sieci/pracownia3/utils.h | 18 ++ semestr-4/sieci/pracownia3/window.c | 42 ++++ semestr-4/sieci/pracownia3/window.h | 24 ++ semestr-4/sieci/pracownia4/p4.pdf | Bin 0 -> 151294 bytes semestr-4/sieci/warsztaty1/w1.pdf | Bin 0 -> 93952 bytes semestr-4/sieci/warsztaty2/w2.pdf | Bin 0 -> 190886 bytes semestr-4/sieci/warsztaty3/w3.pdf | Bin 0 -> 112755 bytes semestr-4/sieci/warsztaty4/w4.pdf | Bin 0 -> 210974 bytes semestr-4/sieci/warsztaty5/w5.pdf | Bin 0 -> 121273 bytes semestr-4/sieci/warsztaty6/w6.pdf | Bin 0 -> 75165 bytes semestr-4/sieci/warsztaty7/lec10.pdf | Bin 0 -> 4477553 bytes semestr-4/sieci/warsztaty7/lec11.pdf | Bin 0 -> 3897828 bytes semestr-4/sieci/warsztaty7/lec12.pdf | Bin 0 -> 4100114 bytes semestr-4/sieci/warsztaty7/lec9.pdf | Bin 0 -> 1890896 bytes semestr-4/sieci/warsztaty7/notes.pdf | Bin 0 -> 67729 bytes semestr-4/sieci/warsztaty7/w1.pdf | Bin 0 -> 93952 bytes semestr-4/sieci/warsztaty7/w7.pdf | Bin 0 -> 101399 bytes semestr-4/sieci/warsztaty8/185551.cpp | 41 ++++ semestr-4/sieci/warsztaty8/185786.cpp | 59 +++++ semestr-4/sieci/warsztaty8/185814.cpp | 64 +++++ semestr-4/sieci/warsztaty8/185880.cpp | 131 ++++++++++ semestr-4/sieci/warsztaty8/185951.cpp | 109 +++++++++ semestr-4/sieci/warsztaty8/185952.cpp | 113 +++++++++ semestr-4/sieci/warsztaty8/185992.cpp | 117 +++++++++ semestr-4/sieci/warsztaty8/186033.cpp | 101 ++++++++ semestr-4/sieci/warsztaty8/186164.cpp | 270 +++++++++++++++++++++ .../Twierdzenie_o_pierwiastkach_wymi.pdf | Bin 0 -> 3774800 bytes semestr-4/sieci/warsztaty8/dat0-check.cpp | 58 +++++ semestr-4/sieci/warsztaty8/dat0-check.e | Bin 0 -> 19240 bytes semestr-4/sieci/warsztaty8/dat0-gen.sh | 107 ++++++++ semestr-4/sieci/warsztaty8/mie1.cpp | 64 +++++ semestr-4/sieci/warsztaty8/prz8-wzo2.cpp | 177 ++++++++++++++ semestr-4/sieci/warsztaty8/prz9.cpp | 97 ++++++++ semestr-4/sieci/warsztaty8/psp0.cpp | 44 ++++ semestr-4/sieci/warsztaty8/w8.pdf | Bin 0 -> 95186 bytes semestr-4/sieci/warsztaty8/wie5.cpp | 158 ++++++++++++ semestr-4/sieci/warsztaty8/wie5.pdf | Bin 0 -> 73787 bytes semestr-4/sieci/wyklady/ASD_kol2_2021-1.pdf | Bin 0 -> 113941 bytes semestr-4/sieci/wyklady/lec1.pdf | Bin 0 -> 8280250 bytes semestr-4/sieci/wyklady/lec13.pdf | Bin 0 -> 6875940 bytes semestr-4/sieci/wyklady/lec2.pdf | Bin 0 -> 5058364 bytes semestr-4/sieci/wyklady/lec3.pdf | Bin 0 -> 8701267 bytes semestr-4/sieci/wyklady/lec4.pdf | Bin 0 -> 5658130 bytes semestr-4/sieci/wyklady/lec5.pdf | Bin 0 -> 4572488 bytes semestr-4/sieci/wyklady/lec6.pdf | Bin 0 -> 3339096 bytes semestr-4/sieci/wyklady/lec7.pdf | Bin 0 -> 1825393 bytes semestr-4/sieci/wyklady/lec8.pdf | Bin 0 -> 2144653 bytes 97 files changed, 4441 insertions(+) create mode 100644 semestr-4/sieci/cwiczenia1/c1.pdf create mode 100644 semestr-4/sieci/cwiczenia1/cw1.pdf create mode 100644 semestr-4/sieci/cwiczenia1/out.pdf create mode 100644 semestr-4/sieci/cwiczenia1/rozw.pdf create mode 100644 semestr-4/sieci/cwiczenia2/.cpp.cpp create mode 100644 semestr-4/sieci/cwiczenia2/c2.pdf create mode 100644 semestr-4/sieci/pracownia1/makefile create mode 100644 semestr-4/sieci/pracownia1/p1.pdf create mode 100644 semestr-4/sieci/pracownia1/traceroute.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka.tar.xz create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/config.h create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.h create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.h create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/makefile create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.h create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/router.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/test.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/utils.c create mode 100644 semestr-4/sieci/pracownia2/franciszek_malinka/utils.h create mode 100644 semestr-4/sieci/pracownia2/p2.pdf create mode 100644 semestr-4/sieci/pracownia2/router/config.h create mode 100644 semestr-4/sieci/pracownia2/router/dist_vector.c create mode 100644 semestr-4/sieci/pracownia2/router/dist_vector.h create mode 100644 semestr-4/sieci/pracownia2/router/linked_list.c create mode 100644 semestr-4/sieci/pracownia2/router/linked_list.h create mode 100644 semestr-4/sieci/pracownia2/router/makefile create mode 100644 semestr-4/sieci/pracownia2/router/network_addr.c create mode 100644 semestr-4/sieci/pracownia2/router/network_addr.h create mode 100644 semestr-4/sieci/pracownia2/router/router.c create mode 100644 semestr-4/sieci/pracownia2/router/test.c create mode 100644 semestr-4/sieci/pracownia2/router/utils.c create mode 100644 semestr-4/sieci/pracownia2/router/utils.h create mode 100755 semestr-4/sieci/pracownia2/udp_client.c create mode 100755 semestr-4/sieci/pracownia2/udp_server.c create mode 100644 semestr-4/sieci/pracownia3/4pkt/config.h create mode 100644 semestr-4/sieci/pracownia3/4pkt/transport.c create mode 100644 semestr-4/sieci/pracownia3/config.h create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka.tar.xz create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/config.h create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/transport.c create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/utils.c create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/utils.h create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/window.c create mode 100644 semestr-4/sieci/pracownia3/franciszek_malinka/window.h create mode 100644 semestr-4/sieci/pracownia3/p3.pdf create mode 100644 semestr-4/sieci/pracownia3/transport.c create mode 100644 semestr-4/sieci/pracownia3/utils.c create mode 100644 semestr-4/sieci/pracownia3/utils.h create mode 100644 semestr-4/sieci/pracownia3/window.c create mode 100644 semestr-4/sieci/pracownia3/window.h create mode 100644 semestr-4/sieci/pracownia4/p4.pdf create mode 100644 semestr-4/sieci/warsztaty1/w1.pdf create mode 100644 semestr-4/sieci/warsztaty2/w2.pdf create mode 100644 semestr-4/sieci/warsztaty3/w3.pdf create mode 100644 semestr-4/sieci/warsztaty4/w4.pdf create mode 100644 semestr-4/sieci/warsztaty5/w5.pdf create mode 100644 semestr-4/sieci/warsztaty6/w6.pdf create mode 100644 semestr-4/sieci/warsztaty7/lec10.pdf create mode 100644 semestr-4/sieci/warsztaty7/lec11.pdf create mode 100644 semestr-4/sieci/warsztaty7/lec12.pdf create mode 100644 semestr-4/sieci/warsztaty7/lec9.pdf create mode 100644 semestr-4/sieci/warsztaty7/notes.pdf create mode 100644 semestr-4/sieci/warsztaty7/w1.pdf create mode 100644 semestr-4/sieci/warsztaty7/w7.pdf create mode 100644 semestr-4/sieci/warsztaty8/185551.cpp create mode 100644 semestr-4/sieci/warsztaty8/185786.cpp create mode 100644 semestr-4/sieci/warsztaty8/185814.cpp create mode 100644 semestr-4/sieci/warsztaty8/185880.cpp create mode 100644 semestr-4/sieci/warsztaty8/185951.cpp create mode 100644 semestr-4/sieci/warsztaty8/185952.cpp create mode 100644 semestr-4/sieci/warsztaty8/185992.cpp create mode 100644 semestr-4/sieci/warsztaty8/186033.cpp create mode 100644 semestr-4/sieci/warsztaty8/186164.cpp create mode 100644 semestr-4/sieci/warsztaty8/Twierdzenie_o_pierwiastkach_wymi.pdf create mode 100644 semestr-4/sieci/warsztaty8/dat0-check.cpp create mode 100644 semestr-4/sieci/warsztaty8/dat0-check.e create mode 100644 semestr-4/sieci/warsztaty8/dat0-gen.sh create mode 100644 semestr-4/sieci/warsztaty8/mie1.cpp create mode 100644 semestr-4/sieci/warsztaty8/prz8-wzo2.cpp create mode 100644 semestr-4/sieci/warsztaty8/prz9.cpp create mode 100644 semestr-4/sieci/warsztaty8/psp0.cpp create mode 100644 semestr-4/sieci/warsztaty8/w8.pdf create mode 100644 semestr-4/sieci/warsztaty8/wie5.cpp create mode 100644 semestr-4/sieci/warsztaty8/wie5.pdf create mode 100644 semestr-4/sieci/wyklady/ASD_kol2_2021-1.pdf create mode 100644 semestr-4/sieci/wyklady/lec1.pdf create mode 100644 semestr-4/sieci/wyklady/lec13.pdf create mode 100644 semestr-4/sieci/wyklady/lec2.pdf create mode 100644 semestr-4/sieci/wyklady/lec3.pdf create mode 100644 semestr-4/sieci/wyklady/lec4.pdf create mode 100644 semestr-4/sieci/wyklady/lec5.pdf create mode 100644 semestr-4/sieci/wyklady/lec6.pdf create mode 100644 semestr-4/sieci/wyklady/lec7.pdf create mode 100644 semestr-4/sieci/wyklady/lec8.pdf (limited to 'semestr-4/sieci') diff --git a/semestr-4/sieci/cwiczenia1/c1.pdf b/semestr-4/sieci/cwiczenia1/c1.pdf new file mode 100644 index 0000000..ace2fa7 Binary files /dev/null and b/semestr-4/sieci/cwiczenia1/c1.pdf differ diff --git a/semestr-4/sieci/cwiczenia1/cw1.pdf b/semestr-4/sieci/cwiczenia1/cw1.pdf new file mode 100644 index 0000000..d217892 Binary files /dev/null and b/semestr-4/sieci/cwiczenia1/cw1.pdf differ diff --git a/semestr-4/sieci/cwiczenia1/out.pdf b/semestr-4/sieci/cwiczenia1/out.pdf new file mode 100644 index 0000000..ea7781d Binary files /dev/null and b/semestr-4/sieci/cwiczenia1/out.pdf differ diff --git a/semestr-4/sieci/cwiczenia1/rozw.pdf b/semestr-4/sieci/cwiczenia1/rozw.pdf new file mode 100644 index 0000000..f2d1a62 Binary files /dev/null and b/semestr-4/sieci/cwiczenia1/rozw.pdf differ diff --git a/semestr-4/sieci/cwiczenia2/.cpp.cpp b/semestr-4/sieci/cwiczenia2/.cpp.cpp new file mode 100644 index 0000000..9938f8b --- /dev/null +++ b/semestr-4/sieci/cwiczenia2/.cpp.cpp @@ -0,0 +1,41 @@ +#include +#define fi first +#define se second +using namespace std; +const int N=1e5; +vector e[N+10]; +int g[N+10]; +int dfs(int x,int k) +{ + int ans=0; + g[x]=0; + for(auto v:e[x]) + { + ans+=dfs(v,k); + if(g[v]+1==k) + { + if(x!=1) + ans++; + g[v]=-1; + } + g[x]=max(g[x],g[v]+1); + } + return ans; +} +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(NULL); + cout.tie(NULL); + int n,k; + cin>>n>>k; + for(int i=1;i>a>>b; + e[b].push_back(a); + } + cout< +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define MAX_TTL 30 +#define MESSAGES_PER_TTL 3 +#define NO_MESSAGES -1 +#define TOO_FEW_MESSAGES -2137 + +void print_as_bytes (unsigned char* buff, ssize_t length) +{ + for (ssize_t i = 0; i < length; i++, buff++) + printf ("%.2x ", *buff); +} + +void debug_received(uint8_t *buffer, struct sockaddr_in *sender, int packet_len) { + char ip_str[20]; + inet_ntop(AF_INET, &(sender->sin_addr), ip_str, sizeof(ip_str)); + + printf("IP packet with ICMP content from: %s\n", ip_str); + struct ip* ip_header = (struct ip*) buffer; + ssize_t ip_header_len = 4 * ip_header->ip_hl; + + printf ("IP header: "); + print_as_bytes (buffer, ip_header_len); + printf("\n"); + + printf ("IP data: "); + print_as_bytes (buffer + ip_header_len, packet_len - ip_header_len); + printf("\n\n"); +} + +struct sockaddr_in get_sockaddr_from_ip(char *ip) { + struct sockaddr_in sock; + bzero(&sock, sizeof(sock)); + sock.sin_family = AF_INET; + if (!inet_pton(AF_INET, ip, &sock.sin_addr)) { + fprintf(stderr, "Given ip is invalid: %s\n", ip); + exit(EXIT_FAILURE); + } + return sock; +} + +int create_raw_icmp_socket() { + int sockfd = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP); + if (sockfd < 0) { + fprintf(stderr, "socket error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + return sockfd; +} + +uint16_t compute_icmp_checksum(const void *buff, int length) +{ + uint32_t sum; + const uint16_t* ptr = buff; + assert (length % 2 == 0); + for (sum = 0; length > 0; length -= 2) + sum += *ptr++; + sum = (sum >> 16) + (sum & 0xffff); + return (uint16_t)(~(sum + (sum >> 16))); +} + +struct icmp create_icmp_header(uint16_t seq) { + struct icmp header; + header.icmp_type = ICMP_ECHO; + header.icmp_code = 0; + header.icmp_id = (uint16_t)getpid(); + header.icmp_seq = seq; + header.icmp_cksum = 0; + header.icmp_cksum = compute_icmp_checksum( + (uint16_t*)&header, sizeof(header)); + + return header; +} + +void send_icmp_packet(int sockfd, struct sockaddr_in *destination, int ttl) { + struct icmp header = create_icmp_header(ttl); + setsockopt(sockfd, IPPROTO_IP, IP_TTL, &ttl, sizeof(int)); + + ssize_t bytes_sent = sendto( + sockfd, + &header, + sizeof(header), + 0, + (struct sockaddr*)destination, + sizeof(*destination) + ); + if (bytes_sent == -1) { + fprintf(stderr, "Error while sending ICMP packet: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } +} + +/* Return ip address of the sender of recceived package */ +ssize_t recv_packet(int sockfd, struct sockaddr_in *sender, uint8_t *buffer) { + socklen_t sender_len = sizeof(*sender); + ssize_t packet_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + + if (packet_len == -1) { + fprintf(stderr, "Error while recieving a packet: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + return packet_len; +} + +void send_icmp_requests(int sockfd, struct sockaddr_in *destination, int ttl, int tries) { + for (int i = 0; i < tries; i++) { + send_icmp_packet(sockfd, destination, ttl); + } +} + +int try_select(int sockfd, struct timeval *tv) { + fd_set descriptors; + FD_ZERO(&descriptors); + FD_SET(sockfd, &descriptors); + return select(sockfd+1, &descriptors, NULL, NULL, tv); +} + +void pretty_print_router(int ttl, struct in_addr *senders, float mean_wait_time, int messages_received) { + char ip_str[20]; + printf("%d.\t", ttl); + if (messages_received == 0) { + printf("*\n"); + } + else { + for (int i = 0; i < messages_received; i++) { + bool already_printed = false; + for (int j = 0; j < i; j++) { + if (senders[i].s_addr == senders[j].s_addr) { + already_printed = true; + break; + } + } + if (already_printed) continue; + inet_ntop(AF_INET, senders + i, ip_str, sizeof(ip_str)); + printf("%-15s ", ip_str); + } + if (messages_received < MESSAGES_PER_TTL) printf("\t???\n"); + else printf("\t%.2fms\n", mean_wait_time); + } +} + +// This function decapsulates important data from the IMCP replies +void get_important_data(uint8_t *buffer, uint8_t *code, uint16_t *id, uint16_t *seq) { + struct ip* ip_header = (struct ip*) buffer; + ssize_t offset = 4 * ip_header->ip_hl; + *code = ((struct icmp *)(buffer + offset))->icmp_type; + if (*code != ICMP_ECHOREPLY && *code != ICMP_TIMXCEED) { + return; + } else if (*code == ICMP_TIMXCEED) { + offset += ICMP_MINLEN; + offset += 4 * ((struct ip *)(buffer + offset))->ip_hl; + *seq = ((struct icmp *)(buffer + offset))->icmp_seq; + *id = ((struct icmp *)(buffer + offset))->icmp_id; + } else { + *seq = ((struct icmp *)(buffer + offset))->icmp_seq; + *id = ((struct icmp *)(buffer + offset))->icmp_id; + } +} + +// timeout in milliseconds +float get_replies(int sockfd, long timeout, int ttl, int *messages_received, struct in_addr *senders) { + struct sockaddr_in sender; + uint8_t buffer[IP_MAXPACKET]; + int ready; + long mean_wait_time = 0; + struct timeval tv; tv.tv_sec = timeout / 1000; tv.tv_usec = 0; + *messages_received = 0; + + while ((ready = try_select(sockfd, &tv))) { + if (ready < 0) { + fprintf(stderr, "Select error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + recv_packet(sockfd, &sender, buffer); + uint8_t icmp_code = 0; + uint16_t seq = 0, id = 0; + + get_important_data(buffer, &icmp_code, &id, &seq); + if (seq == ttl) { + senders[(*messages_received)++] = sender.sin_addr; + mean_wait_time += timeout * 1000 - tv.tv_usec; + + if (*messages_received == MESSAGES_PER_TTL) break; + } + } + // changing from microseconds to miliseconds + return (float)mean_wait_time / 3.0 / 1000.0; +} + +// Core of the program. +void traceroute(struct sockaddr_in *destination) { + int sockfd = create_raw_icmp_socket(), messages_received = 0; + struct in_addr senders[MESSAGES_PER_TTL]; + + for (int ttl = 1; ttl <= MAX_TTL; ++ttl) { + send_icmp_requests(sockfd, destination, ttl, MESSAGES_PER_TTL); + float mean_wait_time = get_replies(sockfd, 1000, ttl, &messages_received, senders); + pretty_print_router(ttl, senders, mean_wait_time, messages_received); + + // what if our packet branched and we got to the destination faster by some path? + // we gotta make a loop, not an if + for (int i = 0; i < messages_received; i++) { + if (senders[i].s_addr == destination->sin_addr.s_addr) { + return; + } + } + } +} + +int main(int argc, char * argv[]) { + if (argc < 2) { + fprintf(stderr, "Usage:\n\t%s [host ip]\n", argv[0]); + return 1; + } + + struct sockaddr_in destination = get_sockaddr_from_ip(argv[1]); + fprintf(stdout, "traceroute to %s, %d hops max\n", argv[1], MAX_TTL); + traceroute(&destination); + + return 0; +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka.tar.xz b/semestr-4/sieci/pracownia2/franciszek_malinka.tar.xz new file mode 100644 index 0000000..ac3b1f7 Binary files /dev/null and b/semestr-4/sieci/pracownia2/franciszek_malinka.tar.xz differ diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/config.h b/semestr-4/sieci/pracownia2/franciszek_malinka/config.h new file mode 100644 index 0000000..ee4eac0 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/config.h @@ -0,0 +1,15 @@ +#ifndef CONFIG_H +#define CONFIG_H + +#define SERVER_PORT 54321 +#define TURN_LEN_S 20 + +#define INFINITY_DIST 16 +#define REACHABILITY_WAIT_TIME 3 + +#define DV_DATAGRAM_LEN 9 + +#define TURN_LEN_MS (1000 * TURN_LEN_S) +#define TURN_LEN_US (1000000 * TURN_LEN_S) + +#endif diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.c b/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.c new file mode 100644 index 0000000..74ae82e --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.c @@ -0,0 +1,114 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "dist_vector.h" +#include +#include +#include + +bool is_connected_directly(struct vector_item item) { + return item.is_connected_directly; +} + +bool is_reachable(struct vector_item item) { + return (item.distance < INFINITY_DIST); +} + +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours) { + for (int i = 0; i < n_cnt; i++) { + struct vector_item new_item; + new_item.network = neighbours[i]; + new_item.distance = INFINITY_DIST; + new_item.is_connected_directly = true; + insert(dv, &new_item, sizeof(new_item)); + } +} + +void update_dv_reachability(list_t *distance_vector) { + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + if(++current->reachable > REACHABILITY_WAIT_TIME) { + if (current->distance >= INFINITY_DIST) { + if (!is_connected_directly(*current)) { + erase_it(distance_vector); + } + } else { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } + iterate(distance_vector); + } +} + +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item) { + bool new_entry = true; + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + + /* If the network is already in the distance vector, then we possibly want to change it: + * - if the new item has better distance than the previous one, then we just want to change it no matter what, + * - if the new item has the same via ip, then we want to check two things: + * - if new item has infinity dist, then we want to set infinity (if it wasn't set, then we want to change reachable to 0) + * - if new item has < inf dist, then we want to change reachable to 0 and set our dist accordingly. + * - else we ignore the entry. + */ + if (get_network_address(current->network).s_addr == get_network_address(new_item.network).s_addr) { + if (current->distance > new_item.distance) { + *current = new_item; + current->reachable = 0; + } else if(current->via_ip.s_addr == new_item.via_ip.s_addr) { + if (new_item.distance >= INFINITY_DIST) { + if (current->distance < INFINITY_DIST) { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } else { + current->distance = new_item.distance; + current->reachable = 0; + } + } + new_entry = false; + } + + iterate(distance_vector); + } + + if (new_entry && new_item.reachable < INFINITY_DIST) { + insert(distance_vector, &new_item, sizeof(new_item)); + } +} + +void print_dv(list_t *distance_vector) { + time_t rawtime; + struct tm * timeinfo; + + time ( &rawtime ); + timeinfo = localtime ( &rawtime ); + char t[100]; + strcpy(t, asctime(timeinfo)); + t[strlen(t) - 1] = 0; + printf("Distance vector [%s]:\n", t); + reset(distance_vector); + while (distance_vector->it != NULL) { + char addr[20], via_addr[20]; + struct vector_item current = *(struct vector_item *)distance_vector->it->data; + struct in_addr net_addr = get_network_address(current.network); + inet_ntop(AF_INET, &net_addr, addr, sizeof(addr)); + printf("%s/%d ", addr, current.network.netmask); + + if (is_reachable(current)) printf("distance %d ", current.distance); + else printf("unreachable "); + + inet_ntop(AF_INET, ¤t.via_ip, via_addr, sizeof(via_addr)); + if (is_connected_directly(current)) printf("connected directly\n"); + else printf("via %s\n", via_addr); + + iterate(distance_vector); + } + printf("\n"); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.h b/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.h new file mode 100644 index 0000000..14159b4 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/dist_vector.h @@ -0,0 +1,36 @@ +#ifndef DIST_VECTOR_H +#define DIST_VECTOR_H + +#include "linked_list.h" +#include "network_addr.h" +#include "config.h" + +/* Item of the distance vector. + * If <> is set to 0, then it means that the network is reachable. + * If <> has positive value, then it indicates that the network was + * unreachable for <> turns. + */ +struct vector_item { + struct network_addr network; + struct in_addr via_ip; + uint16_t distance; + uint8_t reachable; + bool is_connected_directly; +}; + +/* Initis distance vector with given neighbours array. */ +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours); + +/* Returns true if given distance vector item is connected directly, false otherwise. */ +bool is_connected_directly(struct vector_item item); + +/* Updates the distance vector. */ +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item); + +/* Updates reachabilities. */ +void update_dv_reachability(list_t *distance_vector); + +/* Print distance vector. */ +void print_dv(list_t *distance_vector); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.c b/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.c new file mode 100644 index 0000000..16113ac --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.c @@ -0,0 +1,79 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "linked_list.h" +#include +#include + +node_t *_next(node_t *node) { + return (node == NULL) ? NULL : node->next; +} + +void _insert(node_t **head, void *data, size_t data_size) { + node_t *new_node = (node_t *)malloc(sizeof(node_t)); + new_node->data = malloc(data_size); + for (int i = 0; i < data_size; i++) + *(uint8_t *)(new_node->data + i) = *(uint8_t *)(data + i); + new_node->next = *head; + *head = new_node; +} + +void _free_node(node_t *node) { + free(node->data); + free(node); +} + +void _erase(node_t **head) { + node_t *next_node = _next(*head); + _free_node(*head); + *head = next_node; +} + +void _free_list(node_t *head) { + if (head == NULL) return; + _free_list(head->next); + _free_node(head); +} + +list_t create_list() { + list_t ret; + ret.head = NULL; + ret.it = NULL; + return ret; +} + +void insert(list_t *list, void *data, size_t data_size) { + _insert(&list->head, data, data_size); +} + +void erase(list_t *list) { + _erase(&list->head); +} + +void erase_it(list_t *list) { + if(list->it == NULL) return; + if(list->prev_it == NULL) { + erase(list); + reset(list); + return; + } + list->prev_it->next = _next(list->it); + _free_node(list->it); + list->it = list->prev_it->next; +} + +void iterate(list_t *list) { + list->prev_it = list->it; + list->it = _next(list->it); +} + +void reset(list_t *list) { + list->prev_it = NULL; + list->it = list->head; +} + +void free_list(list_t *list) { + _free_list(list->head); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.h b/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.h new file mode 100644 index 0000000..1574b2f --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/linked_list.h @@ -0,0 +1,42 @@ +#ifndef LINKED_LIST_H +#define LINKED_LIST_H + +#include + +typedef struct node { + void *data; + struct node *next; +} node_t; + + +typedef struct list_t { + node_t *head; + node_t *it; + node_t *prev_it; +} list_t; + +/* Creates an empty list. */ +list_t create_list(); + +/* Insert a new node in the begining of a list. */ +void insert(list_t *list, void *data, size_t data_size); + +/* Erases first node from the list. */ +void erase(list_t *list); + +/* Erases element under iterator and sets iterator to the next one. */ +void erase_it(list_t *list); + +/* Moves iterator one step. */ +void iterate(list_t *list); + +/* Resets the iterator. + * Should execute the function after if you want to itarate unless you didnt insert or erase anything from the list. + */ +void reset(list_t *list); + +/* Deletes the whole list. */ +void free_list(list_t *list); + + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/makefile b/semestr-4/sieci/pracownia2/franciszek_malinka/makefile new file mode 100644 index 0000000..bf6a327 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/makefile @@ -0,0 +1,34 @@ +CC := gcc +CFLAGS := -O2 -std=gnu17 -Wall -Wall -Wno-unused-result +TARGET := router +TEST := test +DEPS := config.h + +ODIR := obj +_OBJ := router.o utils.o linked_list.o network_addr.o dist_vector.o +OBJ := $(patsubst %,$(ODIR)/%,$(_OBJ)) + +_TEST_OBJ := test.o linked_list.o +TEST_OBJ := $(patsubst %,$(ODIR)/%,$(_TEST_OBJ)) + + +all: $(TARGET) +test: $(TEST) + +$(ODIR)/%.o: %.c $(DEPS) + $(CC) $(CFLAGS) -c -o $@ $< + +$(TARGET): $(OBJ) + $(CC) -o $@ $^ $(CFLAGS) + +$(TEST): $(TEST_OBJ) + $(CC) -o $@ $^ $(CFLAGS) + +clean: + rm -rf $(TARGET) + rm -rf test + +distclean: + rm -rf $(TARGET) + rm -rf test + rm -rf $(ODIR)/*.o diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.c b/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.c new file mode 100644 index 0000000..cac1060 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.c @@ -0,0 +1,65 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "network_addr.h" +#include +#include +#include + +struct in_addr _get_broadcast_address(struct in_addr addr, uint16_t netmask) { + struct in_addr result = addr; + result.s_addr = ntohl(result.s_addr); + /* bitshift by more than 31 is UB */ + if (netmask == 0) { + result.s_addr = -1; + } + else { + result.s_addr |= ((1 << (32 - netmask)) - 1); + } + result.s_addr = htonl(result.s_addr); + + return result; +} + +struct in_addr _get_network_address(struct in_addr addr, uint16_t netmask) { + struct in_addr result = addr; + result.s_addr = ntohl(result.s_addr); + + if (netmask == 0) { + result.s_addr = 0; + } + else { + result.s_addr &= ~((1 << (32 - netmask)) - 1); + } + result.s_addr = htonl(result.s_addr); + + return result; +} + +struct in_addr get_broadcast_address(struct network_addr na) { + return _get_broadcast_address(na.addr, na.netmask); +} + +struct in_addr get_network_address(struct network_addr na) { + return _get_network_address(na.addr, na.netmask); +} + +void pretty_print_network(struct network_addr na) { + char ip_addr[20]; + inet_ntop(AF_INET, &na.addr, ip_addr, sizeof(ip_addr)); + printf("%s/%d\n", ip_addr, na.netmask); +} + +struct network_addr stona(char *str) { + struct network_addr result; + char addr[20]; + size_t ip_preffix = strcspn(str, "/"); + + strncpy(addr, str, ip_preffix); + addr[ip_preffix] = 0; + inet_pton(AF_INET, addr, &(result.addr)); + result.netmask = atoi(str + ip_preffix + 1); + return result; +} diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.h b/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.h new file mode 100644 index 0000000..6347bbd --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/network_addr.h @@ -0,0 +1,28 @@ +#ifndef ROUTER_ADDR_H +#define ROUTER_ADDR_H + +#include +#include +#include + +/* Network address with netmask. */ +struct network_addr { + struct in_addr addr; + uint8_t netmask; +}; + +typedef struct network_addr router_addr; + +/* Returns broadcast address of a given network. */ +struct in_addr get_broadcast_address(struct network_addr na); + +/* Returns network address of a given network. */ +struct in_addr get_network_address(struct network_addr na); + +/* Prints network_addr via stdio. */ +void pretty_print_network(struct network_addr na); + +/* Converts string of ip in CIDR notation with a netmask to network_addr. */ +struct network_addr stona(char *str); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/router.c b/semestr-4/sieci/pracownia2/franciszek_malinka/router.c new file mode 100644 index 0000000..b5e732c --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/router.c @@ -0,0 +1,60 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "network_addr.h" +#include "utils.h" +#include "dist_vector.h" + +uint16_t read_configuration(struct network_addr** networks, uint16_t **dists) { + uint16_t n; + scanf("%hd", &n); + *networks = malloc(n * sizeof(struct network_addr)); + *dists = malloc(n * sizeof(uint16_t)); + for (int i = 0; i < n; i++) { + char addr[20]; + char _dist[10]; + uint16_t dist; + scanf(" %s %s %hd", addr, _dist, &dist); + (*networks)[i] = stona(addr); + (*dists)[i] = dist; + } + return n; +} + +void router_loop(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists) { + list_t dv = create_list(); + init_dv(&dv, networks_number, networks); + + printf("Starting the router loop...\n"); + for (;;) { + print_dv(&dv); + propagate_distance_vector(sockfd, networks_number, networks, dists, &dv); + listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks, dists, &dv); + } +} + +int main() { + struct network_addr* networks; + uint16_t *dists; + int n = read_configuration(&networks, &dists); + int sockfd = get_socket(); + bind_to_port(sockfd, SERVER_PORT); + + router_loop(sockfd, n, networks, dists); + + close(sockfd); + free(networks); + free(dists); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/test.c b/semestr-4/sieci/pracownia2/franciszek_malinka/test.c new file mode 100644 index 0000000..958ff36 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/test.c @@ -0,0 +1,52 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "linked_list.h" +#include +#include + +/* Prints the list of ints to stdio */ +void print_list(list_t list) { + printf("List: "); + reset(&list); + while (list.it != NULL) { + printf("%d, ", *(int *)(list.it->data)); + iterate(&list); + } + printf("\n"); + reset(&list); +} + +int main() { + int n; + scanf("%d", &n); + list_t list = create_list(); + + for (int i = 0; i < n; i++) { + int t; + scanf("%d", &t); + // insert + if (t == 0) { + int val = 0; + scanf("%d", &val); + insert(&list, &val, sizeof(int)); + reset(&list); + } + if (t == 1) { + iterate(&list); + if (list.it != NULL) + printf("it: %d\n", *(int *)list.it->data); + else printf("End of list.\n"); + } + if (t == 2) { + erase_it(&list); + } + if (t == 3) { + print_list(list); + } + } + + free_list(&list); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/utils.c b/semestr-4/sieci/pracownia2/franciszek_malinka/utils.c new file mode 100644 index 0000000..0c0cae5 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/utils.c @@ -0,0 +1,208 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "utils.h" +#include +#include +#include +#include +#include +#include +#include + +int get_socket() { + int sockfd = socket(AF_INET, SOCK_DGRAM, 0); + if (sockfd < 0) { + fprintf(stderr, "Socket error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + return sockfd; +} + +void bind_to_port(int sockfd, uint16_t port) { + struct sockaddr_in server_address; + bzero(&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + server_address.sin_port = htons(port); + server_address.sin_addr.s_addr = htonl(INADDR_ANY); + + if (bind(sockfd, (struct sockaddr*)&server_address, sizeof(server_address)) < 0) { + fprintf(stderr, "Bind error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + int broadcastPermission = 1; + setsockopt (sockfd, SOL_SOCKET, SO_BROADCAST, (void *)&broadcastPermission, sizeof(broadcastPermission)); +} + +long get_time_interval(struct timespec start, struct timespec finish) { + return S_TO_MS(finish.tv_sec - start.tv_sec) + NS_TO_MS(finish.tv_nsec - start.tv_nsec); +} + +int poll_socket_modify_timeout(int sockfd, int *timeout) { + if (*timeout < 0) { + *timeout = 0; + return 0; + } + + struct pollfd fds; + struct timespec start; + struct timespec finish; + + fds.fd = sockfd; + fds.events = POLLIN; + fds.revents = 0; + + clock_gettime(CLOCK_REALTIME, &start); + int result = poll(&fds, 1, *timeout); + clock_gettime(CLOCK_REALTIME, &finish); + + if (result == -1) { + fprintf(stderr, "poll error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + if (result == 0) { + *timeout = 0; + return 0; + } + + *timeout -= get_time_interval(start, finish); + return result; +} + +size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr network) { + struct sockaddr_in network_address; + bzero (&network_address, sizeof(network_address)); + network_address.sin_family = AF_INET; + network_address.sin_port = htons(SERVER_PORT); + network_address.sin_addr = network; + + return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &network_address, sizeof(network_address)); +} + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + for (int i = 0; i < DV_DATAGRAM_LEN; i++) buffer[i] = 0; + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + return datagram_len; +} + +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender) { + struct vector_item res; + uint32_t ip_addr = *(uint32_t *)buffer; + uint32_t dist = *(uint32_t *)(buffer + 5); + dist = ntohl(dist); + + res.network.addr.s_addr = ip_addr; + res.network.netmask = buffer[4]; + res.is_connected_directly = true; + res.via_ip = sender->sin_addr; + res.distance = (dist < INFINITY_DIST ? dist : INFINITY_DIST); + res.reachable = 0; + + char addr[20]; + inet_ntop(AF_INET, &res.network.addr, addr, sizeof(addr)); + char via[20]; + inet_ntop(AF_INET, &sender->sin_addr, via, sizeof(via)); + return res; +} + +void _get_message(struct vector_item item, char *message) { + *(uint32_t *)message = item.network.addr.s_addr; + message[4] = item.network.netmask; + uint32_t distance = htonl(item.distance >= INFINITY_DIST ? INT_MAX : item.distance); + for (int i = 0; i < 4; i++) { + *(message + 5 + i) = *((char *)(&distance) + i); + } +} + +int _send_item(int sockfd, struct network_addr network, struct vector_item item) { + char message[DV_DATAGRAM_LEN + 1]; + _get_message(item, message); + message[DV_DATAGRAM_LEN] = 0; + ssize_t message_len = DV_DATAGRAM_LEN; + + struct in_addr na = get_broadcast_address(network); + + char addr[20]; + inet_ntop(AF_INET, &na, addr, sizeof(addr)); + + int result; + if ((result = send_message(sockfd, message, message_len, na)) != message_len) { + // fprintf(stderr, "sendto error: %s\n", strerror(errno)); + } + return result; +} + +void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + char buffer[IP_MAXPACKET + 1]; + struct sockaddr_in sender; + + while (poll_socket_modify_timeout(sockfd, &timeout)) { + recv_message(sockfd, buffer, &sender); + struct vector_item new_item = parse_message(buffer, &sender); + + bool is_neighbour = false; + for (int i = 0; i < networks_number; i++) { + if (is_from_network(sender.sin_addr, networks[i])) { + is_neighbour = true; + break; + } + } + + /* Shouldn't happen, just in case. */ + if (!is_neighbour) { + char addr[20]; + inet_ntop(AF_INET, &sender.sin_addr, addr, sizeof(addr)); + fprintf(stderr, "Received datagram from %s, he is in none of my networks, ignoring\n. Maybe his VM routing table is configured incorrectly?\n", addr); + continue; + } + + if (!is_from_network(sender.sin_addr, new_item.network)) { + new_item.is_connected_directly = false; + + for (int i = 0; i < networks_number; i++) { + if (is_from_network(sender.sin_addr, networks[i])) { + new_item.distance += dists[i]; + break; + } + } + } + + update_dv_new_item(dv, new_item); + } + update_dv_reachability(dv); +} + +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + for (int i = 0; i < networks_number; i++) { + reset(dv); + while (dv->it != NULL) { + struct vector_item data = *(struct vector_item *)dv->it->data; + if (!(get_network_address(data.network).s_addr == get_network_address(networks[i]).s_addr) && data.reachable <= REACHABILITY_WAIT_TIME) { + _send_item(sockfd, networks[i], data); + } + iterate(dv); + } + + struct vector_item self_item; + self_item.distance = dists[i]; + self_item.network = networks[i]; + _send_item(sockfd, networks[i], self_item); + } +} + +bool is_from_network(struct in_addr ip_addr, struct network_addr network) { + struct network_addr temp; + temp.addr= ip_addr; + temp.netmask = network.netmask; + return (get_network_address(temp).s_addr == get_network_address(network).s_addr); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/franciszek_malinka/utils.h b/semestr-4/sieci/pracownia2/franciszek_malinka/utils.h new file mode 100644 index 0000000..edf90d0 --- /dev/null +++ b/semestr-4/sieci/pracownia2/franciszek_malinka/utils.h @@ -0,0 +1,52 @@ +#ifndef UTILS_H +#define UTILS_H +#define UTILS_H + +#include "config.h" +#include +#include +#include +#include "network_addr.h" +#include "dist_vector.h" + +#define NS_TO_MS(X) ((long)(X) / (long)1000000) +#define S_TO_MS(X) ((long)(X) * (long)1000) + +/* Returns a UDP socket. */ +int get_socket(); + +/* Binds socket to given port and set the broadcast permission. */ +void bind_to_port(int sockfd, uint16_t port); + +/* Computes the time elapsed between start and finish in miliseconds. */ +long get_time_interval(struct timespec start, struct timespec finish); + +/* Polls given socket with given timeout and changes the timeout accordingly. */ +int poll_socket_modify_timeout(int sockfd, int *timeout); + +/* For debug purposes only. Recieves and prints UDP message. */ +void recv_and_print(int sockfd, int networks_number, struct network_addr *networks); + +/* Sends message in buffer of length buffer_len to addr through given socket. + * IT DOES NOT TERMINATE THE PROGRAM IF SENDTO RETURNS ANY ERRORS! + * One must handle the errors on their own. + */ +size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr addr); + +/* Receive message and write it to buffer. */ +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender); + +/* Parse datagram into a vector item. */ +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender); + +/* Listnes for routers for timeout ms. */ +void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv); + +/* Propagates dv to all connected networks. */ +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv); + +/* Checks if given address is in network range. */ +bool is_from_network(struct in_addr ip_addr, struct network_addr network); + + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/p2.pdf b/semestr-4/sieci/pracownia2/p2.pdf new file mode 100644 index 0000000..f0cc942 Binary files /dev/null and b/semestr-4/sieci/pracownia2/p2.pdf differ diff --git a/semestr-4/sieci/pracownia2/router/config.h b/semestr-4/sieci/pracownia2/router/config.h new file mode 100644 index 0000000..f83c556 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/config.h @@ -0,0 +1,15 @@ +#ifndef CONFIG_H +#define CONFIG_H + +#define SERVER_PORT 54321 +#define TURN_LEN_S 5 + +#define INFINITY_DIST 16 +#define REACHABILITY_WAIT_TIME 3 + +#define DV_DATAGRAM_LEN 9 + +#define TURN_LEN_MS (1000 * TURN_LEN_S) +#define TURN_LEN_US (1000000 * TURN_LEN_S) + +#endif diff --git a/semestr-4/sieci/pracownia2/router/dist_vector.c b/semestr-4/sieci/pracownia2/router/dist_vector.c new file mode 100644 index 0000000..74ae82e --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/dist_vector.c @@ -0,0 +1,114 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "dist_vector.h" +#include +#include +#include + +bool is_connected_directly(struct vector_item item) { + return item.is_connected_directly; +} + +bool is_reachable(struct vector_item item) { + return (item.distance < INFINITY_DIST); +} + +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours) { + for (int i = 0; i < n_cnt; i++) { + struct vector_item new_item; + new_item.network = neighbours[i]; + new_item.distance = INFINITY_DIST; + new_item.is_connected_directly = true; + insert(dv, &new_item, sizeof(new_item)); + } +} + +void update_dv_reachability(list_t *distance_vector) { + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + if(++current->reachable > REACHABILITY_WAIT_TIME) { + if (current->distance >= INFINITY_DIST) { + if (!is_connected_directly(*current)) { + erase_it(distance_vector); + } + } else { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } + iterate(distance_vector); + } +} + +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item) { + bool new_entry = true; + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + + /* If the network is already in the distance vector, then we possibly want to change it: + * - if the new item has better distance than the previous one, then we just want to change it no matter what, + * - if the new item has the same via ip, then we want to check two things: + * - if new item has infinity dist, then we want to set infinity (if it wasn't set, then we want to change reachable to 0) + * - if new item has < inf dist, then we want to change reachable to 0 and set our dist accordingly. + * - else we ignore the entry. + */ + if (get_network_address(current->network).s_addr == get_network_address(new_item.network).s_addr) { + if (current->distance > new_item.distance) { + *current = new_item; + current->reachable = 0; + } else if(current->via_ip.s_addr == new_item.via_ip.s_addr) { + if (new_item.distance >= INFINITY_DIST) { + if (current->distance < INFINITY_DIST) { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } else { + current->distance = new_item.distance; + current->reachable = 0; + } + } + new_entry = false; + } + + iterate(distance_vector); + } + + if (new_entry && new_item.reachable < INFINITY_DIST) { + insert(distance_vector, &new_item, sizeof(new_item)); + } +} + +void print_dv(list_t *distance_vector) { + time_t rawtime; + struct tm * timeinfo; + + time ( &rawtime ); + timeinfo = localtime ( &rawtime ); + char t[100]; + strcpy(t, asctime(timeinfo)); + t[strlen(t) - 1] = 0; + printf("Distance vector [%s]:\n", t); + reset(distance_vector); + while (distance_vector->it != NULL) { + char addr[20], via_addr[20]; + struct vector_item current = *(struct vector_item *)distance_vector->it->data; + struct in_addr net_addr = get_network_address(current.network); + inet_ntop(AF_INET, &net_addr, addr, sizeof(addr)); + printf("%s/%d ", addr, current.network.netmask); + + if (is_reachable(current)) printf("distance %d ", current.distance); + else printf("unreachable "); + + inet_ntop(AF_INET, ¤t.via_ip, via_addr, sizeof(via_addr)); + if (is_connected_directly(current)) printf("connected directly\n"); + else printf("via %s\n", via_addr); + + iterate(distance_vector); + } + printf("\n"); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/dist_vector.h b/semestr-4/sieci/pracownia2/router/dist_vector.h new file mode 100644 index 0000000..14159b4 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/dist_vector.h @@ -0,0 +1,36 @@ +#ifndef DIST_VECTOR_H +#define DIST_VECTOR_H + +#include "linked_list.h" +#include "network_addr.h" +#include "config.h" + +/* Item of the distance vector. + * If <> is set to 0, then it means that the network is reachable. + * If <> has positive value, then it indicates that the network was + * unreachable for <> turns. + */ +struct vector_item { + struct network_addr network; + struct in_addr via_ip; + uint16_t distance; + uint8_t reachable; + bool is_connected_directly; +}; + +/* Initis distance vector with given neighbours array. */ +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours); + +/* Returns true if given distance vector item is connected directly, false otherwise. */ +bool is_connected_directly(struct vector_item item); + +/* Updates the distance vector. */ +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item); + +/* Updates reachabilities. */ +void update_dv_reachability(list_t *distance_vector); + +/* Print distance vector. */ +void print_dv(list_t *distance_vector); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/linked_list.c b/semestr-4/sieci/pracownia2/router/linked_list.c new file mode 100644 index 0000000..16113ac --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/linked_list.c @@ -0,0 +1,79 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "linked_list.h" +#include +#include + +node_t *_next(node_t *node) { + return (node == NULL) ? NULL : node->next; +} + +void _insert(node_t **head, void *data, size_t data_size) { + node_t *new_node = (node_t *)malloc(sizeof(node_t)); + new_node->data = malloc(data_size); + for (int i = 0; i < data_size; i++) + *(uint8_t *)(new_node->data + i) = *(uint8_t *)(data + i); + new_node->next = *head; + *head = new_node; +} + +void _free_node(node_t *node) { + free(node->data); + free(node); +} + +void _erase(node_t **head) { + node_t *next_node = _next(*head); + _free_node(*head); + *head = next_node; +} + +void _free_list(node_t *head) { + if (head == NULL) return; + _free_list(head->next); + _free_node(head); +} + +list_t create_list() { + list_t ret; + ret.head = NULL; + ret.it = NULL; + return ret; +} + +void insert(list_t *list, void *data, size_t data_size) { + _insert(&list->head, data, data_size); +} + +void erase(list_t *list) { + _erase(&list->head); +} + +void erase_it(list_t *list) { + if(list->it == NULL) return; + if(list->prev_it == NULL) { + erase(list); + reset(list); + return; + } + list->prev_it->next = _next(list->it); + _free_node(list->it); + list->it = list->prev_it->next; +} + +void iterate(list_t *list) { + list->prev_it = list->it; + list->it = _next(list->it); +} + +void reset(list_t *list) { + list->prev_it = NULL; + list->it = list->head; +} + +void free_list(list_t *list) { + _free_list(list->head); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/linked_list.h b/semestr-4/sieci/pracownia2/router/linked_list.h new file mode 100644 index 0000000..1574b2f --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/linked_list.h @@ -0,0 +1,42 @@ +#ifndef LINKED_LIST_H +#define LINKED_LIST_H + +#include + +typedef struct node { + void *data; + struct node *next; +} node_t; + + +typedef struct list_t { + node_t *head; + node_t *it; + node_t *prev_it; +} list_t; + +/* Creates an empty list. */ +list_t create_list(); + +/* Insert a new node in the begining of a list. */ +void insert(list_t *list, void *data, size_t data_size); + +/* Erases first node from the list. */ +void erase(list_t *list); + +/* Erases element under iterator and sets iterator to the next one. */ +void erase_it(list_t *list); + +/* Moves iterator one step. */ +void iterate(list_t *list); + +/* Resets the iterator. + * Should execute the function after if you want to itarate unless you didnt insert or erase anything from the list. + */ +void reset(list_t *list); + +/* Deletes the whole list. */ +void free_list(list_t *list); + + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/makefile b/semestr-4/sieci/pracownia2/router/makefile new file mode 100644 index 0000000..bf6a327 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/makefile @@ -0,0 +1,34 @@ +CC := gcc +CFLAGS := -O2 -std=gnu17 -Wall -Wall -Wno-unused-result +TARGET := router +TEST := test +DEPS := config.h + +ODIR := obj +_OBJ := router.o utils.o linked_list.o network_addr.o dist_vector.o +OBJ := $(patsubst %,$(ODIR)/%,$(_OBJ)) + +_TEST_OBJ := test.o linked_list.o +TEST_OBJ := $(patsubst %,$(ODIR)/%,$(_TEST_OBJ)) + + +all: $(TARGET) +test: $(TEST) + +$(ODIR)/%.o: %.c $(DEPS) + $(CC) $(CFLAGS) -c -o $@ $< + +$(TARGET): $(OBJ) + $(CC) -o $@ $^ $(CFLAGS) + +$(TEST): $(TEST_OBJ) + $(CC) -o $@ $^ $(CFLAGS) + +clean: + rm -rf $(TARGET) + rm -rf test + +distclean: + rm -rf $(TARGET) + rm -rf test + rm -rf $(ODIR)/*.o diff --git a/semestr-4/sieci/pracownia2/router/network_addr.c b/semestr-4/sieci/pracownia2/router/network_addr.c new file mode 100644 index 0000000..cac1060 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/network_addr.c @@ -0,0 +1,65 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "network_addr.h" +#include +#include +#include + +struct in_addr _get_broadcast_address(struct in_addr addr, uint16_t netmask) { + struct in_addr result = addr; + result.s_addr = ntohl(result.s_addr); + /* bitshift by more than 31 is UB */ + if (netmask == 0) { + result.s_addr = -1; + } + else { + result.s_addr |= ((1 << (32 - netmask)) - 1); + } + result.s_addr = htonl(result.s_addr); + + return result; +} + +struct in_addr _get_network_address(struct in_addr addr, uint16_t netmask) { + struct in_addr result = addr; + result.s_addr = ntohl(result.s_addr); + + if (netmask == 0) { + result.s_addr = 0; + } + else { + result.s_addr &= ~((1 << (32 - netmask)) - 1); + } + result.s_addr = htonl(result.s_addr); + + return result; +} + +struct in_addr get_broadcast_address(struct network_addr na) { + return _get_broadcast_address(na.addr, na.netmask); +} + +struct in_addr get_network_address(struct network_addr na) { + return _get_network_address(na.addr, na.netmask); +} + +void pretty_print_network(struct network_addr na) { + char ip_addr[20]; + inet_ntop(AF_INET, &na.addr, ip_addr, sizeof(ip_addr)); + printf("%s/%d\n", ip_addr, na.netmask); +} + +struct network_addr stona(char *str) { + struct network_addr result; + char addr[20]; + size_t ip_preffix = strcspn(str, "/"); + + strncpy(addr, str, ip_preffix); + addr[ip_preffix] = 0; + inet_pton(AF_INET, addr, &(result.addr)); + result.netmask = atoi(str + ip_preffix + 1); + return result; +} diff --git a/semestr-4/sieci/pracownia2/router/network_addr.h b/semestr-4/sieci/pracownia2/router/network_addr.h new file mode 100644 index 0000000..6347bbd --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/network_addr.h @@ -0,0 +1,28 @@ +#ifndef ROUTER_ADDR_H +#define ROUTER_ADDR_H + +#include +#include +#include + +/* Network address with netmask. */ +struct network_addr { + struct in_addr addr; + uint8_t netmask; +}; + +typedef struct network_addr router_addr; + +/* Returns broadcast address of a given network. */ +struct in_addr get_broadcast_address(struct network_addr na); + +/* Returns network address of a given network. */ +struct in_addr get_network_address(struct network_addr na); + +/* Prints network_addr via stdio. */ +void pretty_print_network(struct network_addr na); + +/* Converts string of ip in CIDR notation with a netmask to network_addr. */ +struct network_addr stona(char *str); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/router.c b/semestr-4/sieci/pracownia2/router/router.c new file mode 100644 index 0000000..b5e732c --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/router.c @@ -0,0 +1,60 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "network_addr.h" +#include "utils.h" +#include "dist_vector.h" + +uint16_t read_configuration(struct network_addr** networks, uint16_t **dists) { + uint16_t n; + scanf("%hd", &n); + *networks = malloc(n * sizeof(struct network_addr)); + *dists = malloc(n * sizeof(uint16_t)); + for (int i = 0; i < n; i++) { + char addr[20]; + char _dist[10]; + uint16_t dist; + scanf(" %s %s %hd", addr, _dist, &dist); + (*networks)[i] = stona(addr); + (*dists)[i] = dist; + } + return n; +} + +void router_loop(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists) { + list_t dv = create_list(); + init_dv(&dv, networks_number, networks); + + printf("Starting the router loop...\n"); + for (;;) { + print_dv(&dv); + propagate_distance_vector(sockfd, networks_number, networks, dists, &dv); + listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks, dists, &dv); + } +} + +int main() { + struct network_addr* networks; + uint16_t *dists; + int n = read_configuration(&networks, &dists); + int sockfd = get_socket(); + bind_to_port(sockfd, SERVER_PORT); + + router_loop(sockfd, n, networks, dists); + + close(sockfd); + free(networks); + free(dists); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/test.c b/semestr-4/sieci/pracownia2/router/test.c new file mode 100644 index 0000000..958ff36 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/test.c @@ -0,0 +1,52 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "linked_list.h" +#include +#include + +/* Prints the list of ints to stdio */ +void print_list(list_t list) { + printf("List: "); + reset(&list); + while (list.it != NULL) { + printf("%d, ", *(int *)(list.it->data)); + iterate(&list); + } + printf("\n"); + reset(&list); +} + +int main() { + int n; + scanf("%d", &n); + list_t list = create_list(); + + for (int i = 0; i < n; i++) { + int t; + scanf("%d", &t); + // insert + if (t == 0) { + int val = 0; + scanf("%d", &val); + insert(&list, &val, sizeof(int)); + reset(&list); + } + if (t == 1) { + iterate(&list); + if (list.it != NULL) + printf("it: %d\n", *(int *)list.it->data); + else printf("End of list.\n"); + } + if (t == 2) { + erase_it(&list); + } + if (t == 3) { + print_list(list); + } + } + + free_list(&list); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/utils.c b/semestr-4/sieci/pracownia2/router/utils.c new file mode 100644 index 0000000..0c0cae5 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/utils.c @@ -0,0 +1,208 @@ +/* + * Program: router + * Autor: Franciszek Malinka, 316093 + */ + +#include "utils.h" +#include +#include +#include +#include +#include +#include +#include + +int get_socket() { + int sockfd = socket(AF_INET, SOCK_DGRAM, 0); + if (sockfd < 0) { + fprintf(stderr, "Socket error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + return sockfd; +} + +void bind_to_port(int sockfd, uint16_t port) { + struct sockaddr_in server_address; + bzero(&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + server_address.sin_port = htons(port); + server_address.sin_addr.s_addr = htonl(INADDR_ANY); + + if (bind(sockfd, (struct sockaddr*)&server_address, sizeof(server_address)) < 0) { + fprintf(stderr, "Bind error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + int broadcastPermission = 1; + setsockopt (sockfd, SOL_SOCKET, SO_BROADCAST, (void *)&broadcastPermission, sizeof(broadcastPermission)); +} + +long get_time_interval(struct timespec start, struct timespec finish) { + return S_TO_MS(finish.tv_sec - start.tv_sec) + NS_TO_MS(finish.tv_nsec - start.tv_nsec); +} + +int poll_socket_modify_timeout(int sockfd, int *timeout) { + if (*timeout < 0) { + *timeout = 0; + return 0; + } + + struct pollfd fds; + struct timespec start; + struct timespec finish; + + fds.fd = sockfd; + fds.events = POLLIN; + fds.revents = 0; + + clock_gettime(CLOCK_REALTIME, &start); + int result = poll(&fds, 1, *timeout); + clock_gettime(CLOCK_REALTIME, &finish); + + if (result == -1) { + fprintf(stderr, "poll error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + if (result == 0) { + *timeout = 0; + return 0; + } + + *timeout -= get_time_interval(start, finish); + return result; +} + +size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr network) { + struct sockaddr_in network_address; + bzero (&network_address, sizeof(network_address)); + network_address.sin_family = AF_INET; + network_address.sin_port = htons(SERVER_PORT); + network_address.sin_addr = network; + + return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &network_address, sizeof(network_address)); +} + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + for (int i = 0; i < DV_DATAGRAM_LEN; i++) buffer[i] = 0; + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + return datagram_len; +} + +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender) { + struct vector_item res; + uint32_t ip_addr = *(uint32_t *)buffer; + uint32_t dist = *(uint32_t *)(buffer + 5); + dist = ntohl(dist); + + res.network.addr.s_addr = ip_addr; + res.network.netmask = buffer[4]; + res.is_connected_directly = true; + res.via_ip = sender->sin_addr; + res.distance = (dist < INFINITY_DIST ? dist : INFINITY_DIST); + res.reachable = 0; + + char addr[20]; + inet_ntop(AF_INET, &res.network.addr, addr, sizeof(addr)); + char via[20]; + inet_ntop(AF_INET, &sender->sin_addr, via, sizeof(via)); + return res; +} + +void _get_message(struct vector_item item, char *message) { + *(uint32_t *)message = item.network.addr.s_addr; + message[4] = item.network.netmask; + uint32_t distance = htonl(item.distance >= INFINITY_DIST ? INT_MAX : item.distance); + for (int i = 0; i < 4; i++) { + *(message + 5 + i) = *((char *)(&distance) + i); + } +} + +int _send_item(int sockfd, struct network_addr network, struct vector_item item) { + char message[DV_DATAGRAM_LEN + 1]; + _get_message(item, message); + message[DV_DATAGRAM_LEN] = 0; + ssize_t message_len = DV_DATAGRAM_LEN; + + struct in_addr na = get_broadcast_address(network); + + char addr[20]; + inet_ntop(AF_INET, &na, addr, sizeof(addr)); + + int result; + if ((result = send_message(sockfd, message, message_len, na)) != message_len) { + // fprintf(stderr, "sendto error: %s\n", strerror(errno)); + } + return result; +} + +void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + char buffer[IP_MAXPACKET + 1]; + struct sockaddr_in sender; + + while (poll_socket_modify_timeout(sockfd, &timeout)) { + recv_message(sockfd, buffer, &sender); + struct vector_item new_item = parse_message(buffer, &sender); + + bool is_neighbour = false; + for (int i = 0; i < networks_number; i++) { + if (is_from_network(sender.sin_addr, networks[i])) { + is_neighbour = true; + break; + } + } + + /* Shouldn't happen, just in case. */ + if (!is_neighbour) { + char addr[20]; + inet_ntop(AF_INET, &sender.sin_addr, addr, sizeof(addr)); + fprintf(stderr, "Received datagram from %s, he is in none of my networks, ignoring\n. Maybe his VM routing table is configured incorrectly?\n", addr); + continue; + } + + if (!is_from_network(sender.sin_addr, new_item.network)) { + new_item.is_connected_directly = false; + + for (int i = 0; i < networks_number; i++) { + if (is_from_network(sender.sin_addr, networks[i])) { + new_item.distance += dists[i]; + break; + } + } + } + + update_dv_new_item(dv, new_item); + } + update_dv_reachability(dv); +} + +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + for (int i = 0; i < networks_number; i++) { + reset(dv); + while (dv->it != NULL) { + struct vector_item data = *(struct vector_item *)dv->it->data; + if (!(get_network_address(data.network).s_addr == get_network_address(networks[i]).s_addr) && data.reachable <= REACHABILITY_WAIT_TIME) { + _send_item(sockfd, networks[i], data); + } + iterate(dv); + } + + struct vector_item self_item; + self_item.distance = dists[i]; + self_item.network = networks[i]; + _send_item(sockfd, networks[i], self_item); + } +} + +bool is_from_network(struct in_addr ip_addr, struct network_addr network) { + struct network_addr temp; + temp.addr= ip_addr; + temp.netmask = network.netmask; + return (get_network_address(temp).s_addr == get_network_address(network).s_addr); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/router/utils.h b/semestr-4/sieci/pracownia2/router/utils.h new file mode 100644 index 0000000..edf90d0 --- /dev/null +++ b/semestr-4/sieci/pracownia2/router/utils.h @@ -0,0 +1,52 @@ +#ifndef UTILS_H +#define UTILS_H +#define UTILS_H + +#include "config.h" +#include +#include +#include +#include "network_addr.h" +#include "dist_vector.h" + +#define NS_TO_MS(X) ((long)(X) / (long)1000000) +#define S_TO_MS(X) ((long)(X) * (long)1000) + +/* Returns a UDP socket. */ +int get_socket(); + +/* Binds socket to given port and set the broadcast permission. */ +void bind_to_port(int sockfd, uint16_t port); + +/* Computes the time elapsed between start and finish in miliseconds. */ +long get_time_interval(struct timespec start, struct timespec finish); + +/* Polls given socket with given timeout and changes the timeout accordingly. */ +int poll_socket_modify_timeout(int sockfd, int *timeout); + +/* For debug purposes only. Recieves and prints UDP message. */ +void recv_and_print(int sockfd, int networks_number, struct network_addr *networks); + +/* Sends message in buffer of length buffer_len to addr through given socket. + * IT DOES NOT TERMINATE THE PROGRAM IF SENDTO RETURNS ANY ERRORS! + * One must handle the errors on their own. + */ +size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr addr); + +/* Receive message and write it to buffer. */ +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender); + +/* Parse datagram into a vector item. */ +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender); + +/* Listnes for routers for timeout ms. */ +void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv); + +/* Propagates dv to all connected networks. */ +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv); + +/* Checks if given address is in network range. */ +bool is_from_network(struct in_addr ip_addr, struct network_addr network); + + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia2/udp_client.c b/semestr-4/sieci/pracownia2/udp_client.c new file mode 100755 index 0000000..4e7dce4 --- /dev/null +++ b/semestr-4/sieci/pracownia2/udp_client.c @@ -0,0 +1,41 @@ +#include +#include +#include +#include +#include +#include +#include + +int main(int argc, char * argv[]) +{ + if (argc < 2) { + printf("Usage:\n\t%s [server ip]\n", argv[0]); + return -1; + } + + int sockfd = socket(AF_INET, SOCK_DGRAM, 0); + if (sockfd < 0) { + fprintf(stderr, "socket error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + struct sockaddr_in server_address; + bzero (&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + server_address.sin_port = htons(54321); + if (!inet_pton(AF_INET, argv[1], &server_address.sin_addr)) { + printf("Inavlid ip address\n"); + return -1; + } + + char* message = "Hello server!"; + ssize_t message_len = strlen(message); + if (sendto(sockfd, message, message_len, 0, (struct sockaddr*) &server_address, sizeof(server_address)) != message_len) { + fprintf(stderr, "sendto error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + close (sockfd); + return EXIT_SUCCESS; +} + diff --git a/semestr-4/sieci/pracownia2/udp_server.c b/semestr-4/sieci/pracownia2/udp_server.c new file mode 100755 index 0000000..b5ae6d1 --- /dev/null +++ b/semestr-4/sieci/pracownia2/udp_server.c @@ -0,0 +1,59 @@ +#include +#include +#include +#include +#include +#include +#include + +int main() +{ + int sockfd = socket(AF_INET, SOCK_DGRAM, 0); + if (sockfd < 0) { + fprintf(stderr, "socket error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + struct sockaddr_in server_address; + bzero (&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + server_address.sin_port = htons(54321); + server_address.sin_addr.s_addr = htonl(INADDR_ANY); + if (bind (sockfd, (struct sockaddr*)&server_address, sizeof(server_address)) < 0) { + fprintf(stderr, "bind error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + for (;;) { + + struct sockaddr_in sender; + socklen_t sender_len = sizeof(sender); + u_int8_t buffer[IP_MAXPACKET+1]; + + ssize_t datagram_len = recvfrom (sockfd, buffer, IP_MAXPACKET, 0, (struct sockaddr*)&sender, &sender_len); + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + char sender_ip_str[20]; + inet_ntop(AF_INET, &(sender.sin_addr), sender_ip_str, sizeof(sender_ip_str)); + printf ("Received UDP packet from IP address: %s, port: %d\n", sender_ip_str, ntohs(sender.sin_port)); + + buffer[datagram_len] = 0; + printf ("%ld-byte message: +%s+\n", datagram_len, buffer); + + char* reply = "Thank you!"; + ssize_t reply_len = strlen(reply); + if (sendto(sockfd, reply, reply_len, 0, (struct sockaddr*)&sender, sender_len) != reply_len) { + fprintf(stderr, "sendto error: %s\n", strerror(errno)); + return EXIT_FAILURE; + } + + fflush(stdout); + } + + close (sockfd); + return EXIT_SUCCESS; +} + diff --git a/semestr-4/sieci/pracownia3/4pkt/config.h b/semestr-4/sieci/pracownia3/4pkt/config.h new file mode 100644 index 0000000..42ccd89 --- /dev/null +++ b/semestr-4/sieci/pracownia3/4pkt/config.h @@ -0,0 +1,7 @@ +#ifndef CONFIG_H +#define CONFIG_H + +#define DATAGRAM_LEN 1000 +#define HEADER_LEN 40 + +#endif diff --git a/semestr-4/sieci/pracownia3/4pkt/transport.c b/semestr-4/sieci/pracownia3/4pkt/transport.c new file mode 100644 index 0000000..806eb4e --- /dev/null +++ b/semestr-4/sieci/pracownia3/4pkt/transport.c @@ -0,0 +1,152 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "config.h" + +#define NS_TO_MS(X) ((long)(X) / (long)1000000) +#define S_TO_MS(X) ((long)(X) * (long)1000) + +int get_socket() { + int sockfd = socket(AF_INET, SOCK_DGRAM, 0); + if (sockfd < 0) { + fprintf(stderr, "socket error: %s", strerror(errno)); + exit(EXIT_FAILURE); + } + return sockfd; +} + +size_t send_datagram(int sockfd, struct sockaddr_in server_address, char *buffer, size_t buffer_len) { + return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &server_address, sizeof(server_address)); +} + +void send_data_request(int sockfd, struct sockaddr_in server_address, size_t pos, size_t bytes) { + char buffer[40]; + sprintf(buffer, "GET %ld %ld\n", pos, bytes); + size_t buffer_len = strlen(buffer); + if (send_datagram(sockfd, server_address, buffer, buffer_len) != buffer_len) { + fprintf(stderr, "sendto error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } +} + +long get_time_interval(struct timespec start, struct timespec finish) { + return S_TO_MS(finish.tv_sec - start.tv_sec) + NS_TO_MS(finish.tv_nsec - start.tv_nsec); +} + +int poll_socket_modify_timeout(int sockfd, int *timeout) { + if (*timeout < 0) { + *timeout = 0; + return 0; + } + + struct pollfd fds; + struct timespec start; + struct timespec finish; + + fds.fd = sockfd; + fds.events = POLLIN; + fds.revents = 0; + + clock_gettime(CLOCK_REALTIME, &start); + int result = poll(&fds, 1, *timeout); + clock_gettime(CLOCK_REALTIME, &finish); + + if (result == -1) { + fprintf(stderr, "poll error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + if (result == 0) { + *timeout = 0; + return 0; + } + + *timeout -= get_time_interval(start, finish); + return result; +} + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + bzero(buffer, HEADER_LEN + DATAGRAM_LEN); + bzero(sender, sizeof(*sender)); + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + return datagram_len; +} + +inline size_t min(size_t x, size_t y) { return (x +#include +#include +#include +#include +#include +#include +#include "config.h" +#include "window.h" +#include "utils.h" + +size_t send_datagram(int sockfd, struct sockaddr_in server_address, char *buffer, size_t buffer_len) { + return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &server_address, sizeof(server_address)); +} + +void send_data_request(int sockfd, struct sockaddr_in server_address, size_t pos, size_t bytes) { + char buffer[40]; + sprintf(buffer, "GET %ld %ld\n", pos, bytes); + size_t buffer_len = strlen(buffer); + if (send_datagram(sockfd, server_address, buffer, buffer_len) != buffer_len) { + fprintf(stderr, "sendto error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } +} + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + bzero(buffer, HEADER_LEN + DATAGRAM_LEN); + bzero(sender, sizeof(*sender)); + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + return datagram_len; +} + +void request_data(int sockfd, struct sockaddr_in server_address, window_t *w, size_t bytes_writen, size_t remaining_bytes) { + int pos = w->first_pos; + for (int i = 0; i < w->size && i*DATAGRAM_LEN < remaining_bytes; i++) { + if (w->uptodate[pos] == false) { + size_t bytes_to_request = min(DATAGRAM_LEN, remaining_bytes - i*DATAGRAM_LEN); + send_data_request(sockfd, server_address, bytes_writen + i*DATAGRAM_LEN, bytes_to_request); + } + pos = (pos + 1) % w->size; + } +} + +void update_file(FILE *fd, window_t *w, size_t *bytes_writen, size_t *remaining_bytes) { + while (w->uptodate[w->first_pos] && *remaining_bytes > 0) { + // printf("Writing %ld\n", *bytes_writen); + size_t bytes_to_write = min(DATAGRAM_LEN, *remaining_bytes); + fwrite(w->ar[w->first_pos], sizeof(char), bytes_to_write, fd); + *bytes_writen += bytes_to_write; + *remaining_bytes -= bytes_to_write; + shift(w); + } +} + +size_t recv_datagram(int sockfd, char *buffer, struct sockaddr_in server_address) { + struct sockaddr_in sender; + + size_t received_bytes = recv_message(sockfd, buffer, &sender); + if (sender.sin_addr.s_addr != server_address.sin_addr.s_addr || sender.sin_port != server_address.sin_port) { + printf("Smieci!\n"); + return 0; + } + return received_bytes; +} + + +void receive_file(int sockfd, struct sockaddr_in server_address, const char *file_name, size_t remaining_bytes) { + FILE *fd = fopen(file_name, "w"); + if (!fd) { + fprintf(stderr, "fopen error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + size_t bytes_writen = 0; + + size_t recv_pos, recv_len; + char buffer[DATAGRAM_LEN + HEADER_LEN]; + int prev_len = 0; + window_t w; + init_window(&w, WINDOW_SIZE, DATAGRAM_LEN); + + while (remaining_bytes) { + request_data(sockfd, server_address, &w, bytes_writen, remaining_bytes); + int timeout = TIMEOUT; + while (poll_socket_modify_timeout(sockfd, &timeout)) { + size_t received_bytes = recv_datagram(sockfd, buffer, server_address); + if (received_bytes == 0) continue; + sscanf(buffer, "DATA %ld %ld\n", &recv_pos, &recv_len); + if (recv_pos < bytes_writen) continue; + + int pos = (recv_pos - bytes_writen) / DATAGRAM_LEN; + pos = (pos + w.first_pos) % w.size; + if (!w.uptodate[pos]) { + for (int i = 0; i < recv_len; i++) { + w.ar[pos][i] = buffer[i + received_bytes - recv_len]; + } + w.uptodate[pos] = true; + } + update_file(fd, &w, &bytes_writen, &remaining_bytes); + } + + if (prev_len != bytes_writen) { + prev_len = bytes_writen; + printf("%.3f%%\n", 100.0 * (float)(bytes_writen) / (float)(remaining_bytes+bytes_writen)); + } + } + destroy_window(&w); + fclose(fd); +} + +int main(int argc, char *argv[]) { + if (argc != 5) { + printf("Usage:\n\t%s [server ip] [server port] [output file name] [file size]\n", argv[0]); + return -1; + } + + int sockfd = get_socket(); + struct sockaddr_in server_address; + bzero(&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + if (!inet_pton(AF_INET, argv[1], &server_address.sin_addr)) { + fprintf(stderr, "Invalid ip address: %s\n", argv[1]); + return -1; + } + server_address.sin_port = htons(atoi(argv[2])); + if (server_address.sin_port == 0) { + fprintf(stderr, "Invalid port: %s\n", argv[2]); + return -1; + } + + size_t file_len = atoi(argv[4]); + if (file_len == 0) { + printf("File len is 0, nothing to do here.\n"); + return 0; + } + + receive_file(sockfd, server_address, argv[3], file_len); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/franciszek_malinka/utils.c b/semestr-4/sieci/pracownia3/franciszek_malinka/utils.c new file mode 100644 index 0000000..4c2f449 --- /dev/null +++ b/semestr-4/sieci/pracownia3/franciszek_malinka/utils.c @@ -0,0 +1,58 @@ +/* Projekt: Transport + * Autor: Franciszek Malinka 316093 + */ + +#include "utils.h" +#include +#include +#include +#include +#include +#include +#include + +size_t min(size_t x, size_t y) { return (x +#include + +#define NS_TO_MS(X) ((long)(X) / (long)1000000) +#define S_TO_MS(X) ((long)(X) * (long)1000) + +size_t min(size_t x, size_t y); + +int get_socket(); + +long get_time_interval(struct timespec start, struct timespec finish); + +int poll_socket_modify_timeout(int sockfd, int *timeout); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/franciszek_malinka/window.c b/semestr-4/sieci/pracownia3/franciszek_malinka/window.c new file mode 100644 index 0000000..c8bffad --- /dev/null +++ b/semestr-4/sieci/pracownia3/franciszek_malinka/window.c @@ -0,0 +1,42 @@ +/* Projekt: Transport + * Autor: Franciszek Malinka 316093 + */ + +#include "window.h" +#include +#include + +void init_window(window_t *w, int window_size, int window_width) { + w->ar = malloc(window_size * sizeof(char *)); + for (int i = 0; i < window_size; i++) + w->ar[i] = malloc(window_width * sizeof(char)); + w->uptodate = malloc(window_size); + bzero (w->uptodate, window_size); + w->first_pos = 0; + w->size = window_size; +} + +void destroy_window(window_t *w) { + for (int i = 0; i < w->size; i++) + free(w->ar[i]); + free(w->ar); + free(w->uptodate); +} + +void shift_while_uptodate(window_t *w) { + while (w->uptodate[w->first_pos]) { + w->uptodate[w->first_pos] = false; + w->first_pos = (w->first_pos + 1) % w->size; + } +} + +void shift(window_t *w) { + w->uptodate[w->first_pos] = false; + w->first_pos = (w->first_pos + 1) % w->size; +} + +void update(window_t *w, int pos, char *buffer, size_t buf_size) { + pos = (w->first_pos + pos) % w->size; + for (int i = 0; i < buf_size; i++) w->ar[pos][i] = buffer[i]; + w->uptodate[pos] = true; +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/franciszek_malinka/window.h b/semestr-4/sieci/pracownia3/franciszek_malinka/window.h new file mode 100644 index 0000000..63e89cc --- /dev/null +++ b/semestr-4/sieci/pracownia3/franciszek_malinka/window.h @@ -0,0 +1,24 @@ +#ifndef WINDOW_H +#define WINDOW_H + +#include +#include + +typedef struct { + char **ar; + bool *uptodate; + int size; + int first_pos; +} window_t; + +void init_window(window_t *w, int window_size, int window_width); + +void destroy_window(window_t *w); + +void shift_while_uptodate(window_t *w); + +void shift(window_t *w); + +void update(window_t *w, int pos, char *buffer, size_t buf_size); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/p3.pdf b/semestr-4/sieci/pracownia3/p3.pdf new file mode 100644 index 0000000..14f1261 Binary files /dev/null and b/semestr-4/sieci/pracownia3/p3.pdf differ diff --git a/semestr-4/sieci/pracownia3/transport.c b/semestr-4/sieci/pracownia3/transport.c new file mode 100644 index 0000000..9226d69 --- /dev/null +++ b/semestr-4/sieci/pracownia3/transport.c @@ -0,0 +1,149 @@ +/* Projekt: Transport + * Autor: Franciszek Malinka 316093 + */ + +#include +#include +#include +#include +#include +#include +#include +#include "config.h" +#include "window.h" +#include "utils.h" + +size_t send_datagram(int sockfd, struct sockaddr_in server_address, char *buffer, size_t buffer_len) { + return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &server_address, sizeof(server_address)); +} + +void send_data_request(int sockfd, struct sockaddr_in server_address, size_t pos, size_t bytes) { + char buffer[40]; + sprintf(buffer, "GET %ld %ld\n", pos, bytes); + size_t buffer_len = strlen(buffer); + if (send_datagram(sockfd, server_address, buffer, buffer_len) != buffer_len) { + fprintf(stderr, "sendto error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } +} + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + bzero(buffer, HEADER_LEN + DATAGRAM_LEN); + bzero(sender, sizeof(*sender)); + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + + return datagram_len; +} + +void request_data(int sockfd, struct sockaddr_in server_address, window_t *w, size_t bytes_writen, size_t remaining_bytes) { + int pos = w->first_pos; + for (int i = 0; i < w->size && i*DATAGRAM_LEN < remaining_bytes; i++) { + if (w->uptodate[pos] == false) { + size_t bytes_to_request = min(DATAGRAM_LEN, remaining_bytes - i*DATAGRAM_LEN); + send_data_request(sockfd, server_address, bytes_writen + i*DATAGRAM_LEN, bytes_to_request); + } + pos = (pos + 1) % w->size; + } +} + +void update_file(FILE *fd, window_t *w, size_t *bytes_writen, size_t *remaining_bytes) { + while (w->uptodate[w->first_pos] && *remaining_bytes > 0) { + // printf("Writing %ld\n", *bytes_writen); + size_t bytes_to_write = min(DATAGRAM_LEN, *remaining_bytes); + fwrite(w->ar[w->first_pos], sizeof(char), bytes_to_write, fd); + *bytes_writen += bytes_to_write; + *remaining_bytes -= bytes_to_write; + shift(w); + } +} + +size_t recv_datagram(int sockfd, char *buffer, struct sockaddr_in server_address) { + struct sockaddr_in sender; + + size_t received_bytes = recv_message(sockfd, buffer, &sender); + if (sender.sin_addr.s_addr != server_address.sin_addr.s_addr || sender.sin_port != server_address.sin_port) { + printf("Smieci!\n"); + return 0; + } + return received_bytes; +} + + +void receive_file(int sockfd, struct sockaddr_in server_address, const char *file_name, size_t remaining_bytes) { + FILE *fd = fopen(file_name, "w"); + if (!fd) { + fprintf(stderr, "fopen error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + size_t bytes_writen = 0; + + size_t recv_pos, recv_len; + char buffer[DATAGRAM_LEN + HEADER_LEN]; + int prev_len = 0; + window_t w; + init_window(&w, WINDOW_SIZE, DATAGRAM_LEN); + + while (remaining_bytes) { + request_data(sockfd, server_address, &w, bytes_writen, remaining_bytes); + int timeout = TIMEOUT; + while (poll_socket_modify_timeout(sockfd, &timeout)) { + size_t received_bytes = recv_datagram(sockfd, buffer, server_address); + if (received_bytes == 0) continue; + sscanf(buffer, "DATA %ld %ld\n", &recv_pos, &recv_len); + if (recv_pos < bytes_writen) continue; + + int pos = (recv_pos - bytes_writen) / DATAGRAM_LEN; + pos = (pos + w.first_pos) % w.size; + if (!w.uptodate[pos]) { + for (int i = 0; i < recv_len; i++) { + w.ar[pos][i] = buffer[i + received_bytes - recv_len]; + } + w.uptodate[pos] = true; + } + update_file(fd, &w, &bytes_writen, &remaining_bytes); + } + + if (prev_len != bytes_writen) { + prev_len = bytes_writen; + printf("%.3f%%\n", 100.0 * (float)(bytes_writen) / (float)(remaining_bytes+bytes_writen)); + } + } + destroy_window(&w); + fclose(fd); +} + +int main(int argc, char *argv[]) { + if (argc != 5) { + printf("Usage:\n\t%s [server ip] [server port] [output file name] [file size]\n", argv[0]); + return -1; + } + + int sockfd = get_socket(); + struct sockaddr_in server_address; + bzero(&server_address, sizeof(server_address)); + server_address.sin_family = AF_INET; + if (!inet_pton(AF_INET, argv[1], &server_address.sin_addr)) { + fprintf(stderr, "Invalid ip address: %s\n", argv[1]); + return -1; + } + server_address.sin_port = htons(atoi(argv[2])); + if (server_address.sin_port == 0) { + fprintf(stderr, "Invalid port: %s\n", argv[2]); + return -1; + } + + size_t file_len = atoi(argv[4]); + if (file_len == 0) { + printf("File len is 0, nothing to do here.\n"); + return 0; + } + + receive_file(sockfd, server_address, argv[3], file_len); +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/utils.c b/semestr-4/sieci/pracownia3/utils.c new file mode 100644 index 0000000..4c2f449 --- /dev/null +++ b/semestr-4/sieci/pracownia3/utils.c @@ -0,0 +1,58 @@ +/* Projekt: Transport + * Autor: Franciszek Malinka 316093 + */ + +#include "utils.h" +#include +#include +#include +#include +#include +#include +#include + +size_t min(size_t x, size_t y) { return (x +#include + +#define NS_TO_MS(X) ((long)(X) / (long)1000000) +#define S_TO_MS(X) ((long)(X) * (long)1000) + +size_t min(size_t x, size_t y); + +int get_socket(); + +long get_time_interval(struct timespec start, struct timespec finish); + +int poll_socket_modify_timeout(int sockfd, int *timeout); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/window.c b/semestr-4/sieci/pracownia3/window.c new file mode 100644 index 0000000..c8bffad --- /dev/null +++ b/semestr-4/sieci/pracownia3/window.c @@ -0,0 +1,42 @@ +/* Projekt: Transport + * Autor: Franciszek Malinka 316093 + */ + +#include "window.h" +#include +#include + +void init_window(window_t *w, int window_size, int window_width) { + w->ar = malloc(window_size * sizeof(char *)); + for (int i = 0; i < window_size; i++) + w->ar[i] = malloc(window_width * sizeof(char)); + w->uptodate = malloc(window_size); + bzero (w->uptodate, window_size); + w->first_pos = 0; + w->size = window_size; +} + +void destroy_window(window_t *w) { + for (int i = 0; i < w->size; i++) + free(w->ar[i]); + free(w->ar); + free(w->uptodate); +} + +void shift_while_uptodate(window_t *w) { + while (w->uptodate[w->first_pos]) { + w->uptodate[w->first_pos] = false; + w->first_pos = (w->first_pos + 1) % w->size; + } +} + +void shift(window_t *w) { + w->uptodate[w->first_pos] = false; + w->first_pos = (w->first_pos + 1) % w->size; +} + +void update(window_t *w, int pos, char *buffer, size_t buf_size) { + pos = (w->first_pos + pos) % w->size; + for (int i = 0; i < buf_size; i++) w->ar[pos][i] = buffer[i]; + w->uptodate[pos] = true; +} \ No newline at end of file diff --git a/semestr-4/sieci/pracownia3/window.h b/semestr-4/sieci/pracownia3/window.h new file mode 100644 index 0000000..63e89cc --- /dev/null +++ b/semestr-4/sieci/pracownia3/window.h @@ -0,0 +1,24 @@ +#ifndef WINDOW_H +#define WINDOW_H + +#include +#include + +typedef struct { + char **ar; + bool *uptodate; + int size; + int first_pos; +} window_t; + +void init_window(window_t *w, int window_size, int window_width); + +void destroy_window(window_t *w); + +void shift_while_uptodate(window_t *w); + +void shift(window_t *w); + +void update(window_t *w, int pos, char *buffer, size_t buf_size); + +#endif \ No newline at end of file diff --git a/semestr-4/sieci/pracownia4/p4.pdf b/semestr-4/sieci/pracownia4/p4.pdf new file mode 100644 index 0000000..bdaa771 Binary files /dev/null and b/semestr-4/sieci/pracownia4/p4.pdf differ diff --git a/semestr-4/sieci/warsztaty1/w1.pdf b/semestr-4/sieci/warsztaty1/w1.pdf new file mode 100644 index 0000000..5b50091 Binary files /dev/null and b/semestr-4/sieci/warsztaty1/w1.pdf differ diff --git a/semestr-4/sieci/warsztaty2/w2.pdf b/semestr-4/sieci/warsztaty2/w2.pdf new file mode 100644 index 0000000..60cdc33 Binary files /dev/null and b/semestr-4/sieci/warsztaty2/w2.pdf differ diff --git a/semestr-4/sieci/warsztaty3/w3.pdf b/semestr-4/sieci/warsztaty3/w3.pdf new file mode 100644 index 0000000..b0266ad Binary files /dev/null and b/semestr-4/sieci/warsztaty3/w3.pdf differ diff --git a/semestr-4/sieci/warsztaty4/w4.pdf b/semestr-4/sieci/warsztaty4/w4.pdf new file mode 100644 index 0000000..1d6b54d Binary files /dev/null and b/semestr-4/sieci/warsztaty4/w4.pdf differ diff --git a/semestr-4/sieci/warsztaty5/w5.pdf b/semestr-4/sieci/warsztaty5/w5.pdf new file mode 100644 index 0000000..e55fb7b Binary files /dev/null and b/semestr-4/sieci/warsztaty5/w5.pdf differ diff --git a/semestr-4/sieci/warsztaty6/w6.pdf b/semestr-4/sieci/warsztaty6/w6.pdf new file mode 100644 index 0000000..2f6b6c9 Binary files /dev/null and b/semestr-4/sieci/warsztaty6/w6.pdf differ diff --git a/semestr-4/sieci/warsztaty7/lec10.pdf b/semestr-4/sieci/warsztaty7/lec10.pdf new file mode 100644 index 0000000..d64feee Binary files /dev/null and b/semestr-4/sieci/warsztaty7/lec10.pdf differ diff --git a/semestr-4/sieci/warsztaty7/lec11.pdf b/semestr-4/sieci/warsztaty7/lec11.pdf new file mode 100644 index 0000000..b48a825 Binary files /dev/null and b/semestr-4/sieci/warsztaty7/lec11.pdf differ diff --git a/semestr-4/sieci/warsztaty7/lec12.pdf b/semestr-4/sieci/warsztaty7/lec12.pdf new file mode 100644 index 0000000..8bb1580 Binary files /dev/null and b/semestr-4/sieci/warsztaty7/lec12.pdf differ diff --git a/semestr-4/sieci/warsztaty7/lec9.pdf b/semestr-4/sieci/warsztaty7/lec9.pdf new file mode 100644 index 0000000..c7601b3 Binary files /dev/null and b/semestr-4/sieci/warsztaty7/lec9.pdf differ diff --git a/semestr-4/sieci/warsztaty7/notes.pdf b/semestr-4/sieci/warsztaty7/notes.pdf new file mode 100644 index 0000000..a02808f Binary files /dev/null and b/semestr-4/sieci/warsztaty7/notes.pdf differ diff --git a/semestr-4/sieci/warsztaty7/w1.pdf b/semestr-4/sieci/warsztaty7/w1.pdf new file mode 100644 index 0000000..5b50091 Binary files /dev/null and b/semestr-4/sieci/warsztaty7/w1.pdf differ diff --git a/semestr-4/sieci/warsztaty7/w7.pdf b/semestr-4/sieci/warsztaty7/w7.pdf new file mode 100644 index 0000000..62f35c2 Binary files /dev/null and b/semestr-4/sieci/warsztaty7/w7.pdf differ diff --git a/semestr-4/sieci/warsztaty8/185551.cpp b/semestr-4/sieci/warsztaty8/185551.cpp new file mode 100644 index 0000000..5d5af6a --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185551.cpp @@ -0,0 +1,41 @@ +#include +using namespace std; +typedef long long ll; +#define pb push_back +#define st first +#define nd second + +const int N = 1000007; + +map M; +ll tab[N]; +vector v; +queue > q; + +int main () { + ios_base::sync_with_stdio(false); + cin.tie(0); + ll n, a=-1, b=0; + M[0]=1; + cin>>n; + for(int i=0; i>tab[i]; + } + sort(tab, tab+n); + for(int i=0; i0) q.push({u.st+a, u.nd}); + } + while(!q.empty()) M[q.front().st]+=q.front().nd, q.pop(); + v.pb(a); + } + b++; + } + cout< +using namespace std; + +string jednosci[20] = {"", "jeden ", "dwa ", "trzy ", "cztery ", "piec ", "szesc ", "siedem ", "osiem ", "dziewiec "}; +string setki[20] = {"", "sto ", "dwiescie ", "trzysta ", "czterysta ", "piecset ", "szescset ", "siedemset ", "osiemset ", "dziewiecset "}; +string dziesiatki[20] = {"", "", "dwadziescia ", "trzydziesci ", "czterdziesci ", "piecdziesiat ", "szescdziesiat ", "siedemdziesiat ", "osiemdziesiat ", "dziewiecdziesiat "}; +string nastki[20] = {"dziesiec ", "jedenascie ", "dwanascie ", "trzynascie ", "czternascie ", "pietnascie ", "szesnascie ", "siedemnascie ", "osiemnascie ", "dziewietnascie "}; +string mil[20] = {"milionow ", "milionow ", "miliony ", "miliony ", "miliony ", "milionow ", "milionow ", "milionow ", "milionow ", "milionow "}; +string tys[20] = {"tysiecy ", "tysiecy ", "tysiace ", "tysiace ", "tysiace ", "tysiecy ", "tysiecy ", "tysiecy ", "tysiecy ", "tysiecy "}; + +string do_stu(int n) { + string odp=""; + if(n!=0) { + odp+=setki[n/100]; + int dzies=(n/10)%10; + if(dzies!=1) { + odp+=dziesiatki[dzies]; + odp+=jednosci[n%10]; + } + else odp+=nastki[n%10]; + } + return odp; +} + +string miliony(int n) { + string odp=""; + if(n==1) return "milion "; + if(n==0) return ""; + odp+=do_stu(n); + int dzies = (n/10)%10; + if(dzies==1) odp+="milionow "; + else odp+=mil[n%10]; + return odp; +} + +string tysiace(int n) { + string odp=""; + if(n==1) return "tysiac "; + if(n==0) return ""; + odp+=do_stu(n); + int dzies = (n/10)%10; + if(dzies==1) odp+="tysiecy "; + else odp+=tys[n%10]; + return odp; +} + +int main () { + ios_base::sync_with_stdio(false); + cin.tie(0); + int n; + cin>>n; + if(n==0) { + cout<<"zero"; + return 0; + } + string wynik= miliony(n/1000000)+tysiace((n/1000)%1000)+do_stu(n%1000); + cout< +using namespace std; + +string Jedn[] = {"","jeden","dwa","trzy","cztery","piec","szesc","siedem","osiem","dziewiec"}; +string Nasc[] = {"dziesiec","jedenascie","dwanascie","trzynascie","czternascie","pietnascie","szesnascie","siedemnascie","osiemnascie","dziewietnascie"}; +string Dzie[] = {"","","dwadziescia","trzydziesci","czterdziesci","piecdziesiat","szescdziesiat","siedemdziesiat","osiemdziesiat","dziewiecdziesiat"}; +string Setk[] = {"","sto","dwiescie","trzysta","czterysta","piecset","szescset","siedemset","osiemset","dziewiecset"}; + +string fragment(int liczba){ + string ret; + int s = liczba/100, d = (liczba/10)%10, j = liczba%10; + ret += Setk[s]; + if(Setk[s] != "") ret += " "; + + if(d == 1) ret += Nasc[j]; + else{ + ret += Dzie[d]; + if(Dzie[d] != "") ret += " "; + ret += Jedn[j]; + } + return ret; +} + +string miliony(int ile){ + if(ile == 0) return ""; + if(ile == 1) return "milion"; + int d = ile%10, j = (ile/10)%10; + if((d >= 2 && d <= 4) && j != 1) return "miliony"; + return "milionow"; +} + +string tysiace(int ile){ + if(ile == 0) return ""; + if(ile == 1) return "tysiac"; + int d = ile%10, j = (ile/10)%10; + if((d >= 2 && d <= 4) && j != 1) return "tysiace"; + return "tysiecy"; +} + +int main(){ + int n; + string wyr; + cin >> n; + int mln = n/1000000, tys = (n/1000)%1000, jed = n%1000; + + if(n == 0){ + cout << "zero"; + return 0; + } + + wyr = fragment(mln); + if(wyr != "jeden") cout << wyr; + if(wyr != "" && wyr != "jeden") cout << " "; + cout << miliony(mln); + if(wyr != "") cout << " "; + + wyr = fragment(tys); + if(wyr != "jeden") cout << wyr; + if(wyr != "" && wyr != "jeden") cout << " "; + cout << tysiace(tys); + if(wyr != "") cout << " "; + + cout << fragment(jed); +} \ No newline at end of file diff --git a/semestr-4/sieci/warsztaty8/185880.cpp b/semestr-4/sieci/warsztaty8/185880.cpp new file mode 100644 index 0000000..2643585 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185880.cpp @@ -0,0 +1,131 @@ +#include +using namespace std; + +void dziesiatki ( int x); +void sety ( int x); + +string od1do9[]= { "zero", "jeden", "dwa", "trzy", "cztery", "piec", "szesc", "siedem", "osiem", "dziewiec"}; +string od10do19[]= { "dziesiec", "jedynascie", "dwanascie", "trzynascie", "czternascie", "pietnascie", "szesnascie", "siedemnaœcie", "osiemnascie", "dziewietnascie"}; +string od20do90[]= {"", "dwadziescia", "trzydziesci", "czterdziesci", "piecdziesciat", "szescdziesciat", "siedemdziesiat", "osiemdziesiat", "dziewiecdziesiat"}; +string od200do900[]= { "", "dwiescie", "trzysta", "czterysta", "piecset", "szescset", "siedemset", "osiemset", "dziewiecset"}; + +void miliony ( int x) { + if ( x==1) { + cout<<"milion "; + return; + } + + dziesiatki(x); + if ( x >= 2 && x<=4) { + cout<<"miliony "; + } else { + cout<<"milionow "; + } +} + +void tysiace ( int x) { + if ( x==1) { + cout<<"tysiac "; + } else { + if ( x==100) { + cout<<"sto tysiecy"; + } else { + if ( x<10) { + if ( x<=4) { + cout<=10 && x<=99) { + dziesiatki(x); + } else { + cout<=10) { + dziesiatki(x); + } + else { + if ( x%100>=1 && x%100<=9) { + cout<=10) { + dziesiatki(x); + } else { + if (x!=0) { + cout<>n; + if ( n>=1000000) { + miliony ( n/1000000); + } + n=n%1000000; + if ( n>=1000) { + tysiace( n/1000); + } + n=n%1000; + + sety (n); +} + +//b³edy 999999 diff --git a/semestr-4/sieci/warsztaty8/185951.cpp b/semestr-4/sieci/warsztaty8/185951.cpp new file mode 100644 index 0000000..df7c356 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185951.cpp @@ -0,0 +1,109 @@ +#include +using namespace std; + +int max_miesiac[12]={31,28,31,30,31,30,31,31,30,31,30,31}; +string dzien[2]={"dzien","dni"}; +string godziny[3]={"godzina","godziny","godzin"}; +string minuty[3]={"minuta","minuty","minut"}; +string sekundy[3]={"sekunda","sekundy","sekund"}; + +string wypisz(int a, char wyz) +{ + int dz=a/10; + int j=a%10; + if(wyz=='g'){ + if(j==1 and dz==0){ + return godziny[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return godziny[1]; + }else{ + return godziny[2]; + } + } + } + if(wyz=='m'){ + if(j==1 and dz==0){ + return minuty[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return minuty[1]; + }else{ + return minuty[2]; + } + } + } + if(wyz=='s'){ + if(j==1 and dz==0){ + return sekundy[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return sekundy[1]; + }else{ + return sekundy[2]; + } + } + } + return ""; +} + +int main(){ +int rok,mies,dni,godz,mi,sek; +long long time1=0,time2=0; +char p; +cin>>rok>>p>>mies>>p>>dni>>godz>>p>>mi>>p>>sek; +time1=time1+sek+(mi*60)+(godz*3600)+((dni-1)*86400); +for(int i=0;i>rok>>p>>mies>>p>>dni>>godz>>p>>mi>>p>>sek; +cin>>p; +time2=time2+sek+(mi*60)+(godz*3600)+((dni-1)*86400); +for(int i=0;i0){ + if(dni==1){ + cout<0){ + cout<0){ + cout<0){ + cout< +using namespace std; + +int tab[13]= {31,28,31,30,31,30,31,31,30,31,30,31}; + +int czas(string dt,string g) +{ + int lata,msc,dni; + long long c1,c2; + lata=dt[0]*1000+dt[1]*100+dt[2]*10+dt[3]-'0'*1111-1900; + msc=dt[5]*10+dt[6]-11*'0'; + dni=0; + c1=(dt[8]*10+dt[9]-11*'0'-1)*86400; + c1+=(g[0]*10+g[1]-11*'0')*3600; + c1+=(g[3]*10+g[4]-11*'0')*60; + c1+=g[6]*10+g[7]-11*'0'; + for(int i=0; i> dt >> g; + long long w1=czas(dt,g); + cin >> dt >> g; + int n; + cin >> n; + long long w2=czas(dt,g); + long long w=w2-w1; + int d=w/86400; + w%=86400; + int h=w/3600; + w%=3600; + int m=w/60; + w%=60; + int s=w; + if(d!=0) + { + cout << d << ' '; + if(d==1) + { + cout << "dzien "; + } + else + { + cout << "dni "; + } + } + if(h!=0) + { + cout << h << ' '; + if(h==1) + { + cout << "godzina "; + } + else if(h%10>=2 && h%10<=4 && (h<=11 || h>=15)) + { + cout << "godziny "; + } + else + { + cout << "godzin "; + } + + } + if(m!=0) + { + cout << m << ' '; + if(m==1) + { + cout << "minuta "; + } + else if(m%10>=2 && m%10<=4 && (m<=11 || m>=15)) + { + cout << "minuty "; + } + else + { + cout << "minut "; + } + + } + if(s!=0) + { + cout << s << ' '; + if(s==1) + { + cout << "sekunda "; + } + else if(h%10>=2 && h%10<=4 && (h<=11 || h>=15)) + { + cout << "sekundy "; + } + else + { + cout << "sekund "; + } + + } + cout << "\n"; +} + + + + diff --git a/semestr-4/sieci/warsztaty8/185992.cpp b/semestr-4/sieci/warsztaty8/185992.cpp new file mode 100644 index 0000000..491f748 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185992.cpp @@ -0,0 +1,117 @@ +#include +using namespace std; + +void dziesiatki ( int x); +void sety ( int x); + +string od1do9[]= { "zero", "jeden", "dwa", "trzy", "cztery", "piec", "szesc", "siedem", "osiem", "dziewiec"}; +string od10do19[]= { "dziesiec", "jedenascie", "dwanascie", "trzynascie", "czternascie", "pietnascie", "szesnascie", "siedemnascie", "osiemnascie", "dziewietnascie"}; +string od20do90[]= {"", "dwadziescia", "trzydziesci", "czterdziesci", "piecdziesiat", "szescdziesiat", "siedemdziesiat", "osiemdziesiat", "dziewiecdziesiat"}; +string od200do900[]= { "", "dwiescie", "trzysta", "czterysta", "piecset", "szescset", "siedemset", "osiemset", "dziewiecset"}; + +void miliony ( int x) { + if ( x==1) { + cout<<"milion "; + return; + } + dziesiatki(x); + if ( ( x >= 2 && x<=4) || ( x%10 >= 2 && x%10<=4) ) { + cout<<"miliony "; + return; + } else { + cout<<"milionow "; + return; + } + +} + +void tysiace ( int x) { + if ( x==1) { + cout<<"tysiac "; + return; + } + if ( x==100) { + cout<<"sto tysiecy"; + return; + } + if ( x<10) { + if ( x<=4) { + cout<=10 && x<=99) { + dziesiatki(x); + if ( x%10>=2 && x%10<=4) { + cout<<"tysiece "; + return; + } + cout<<"tysiecy "; + return; + } + cout<=10 ) { + dziesiatki(x); + return; + } + if (x!=0 && x<10) { + cout<>n; + if ( n>=1000000) { + miliony ( n/1000000); + } + n=n%1000000; + if ( n>=1000) { + tysiace( n/1000); + } + n=n%1000; + sety (n); +} diff --git a/semestr-4/sieci/warsztaty8/186033.cpp b/semestr-4/sieci/warsztaty8/186033.cpp new file mode 100644 index 0000000..85911e3 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/186033.cpp @@ -0,0 +1,101 @@ +#include + +using namespace std; + +#define st first +#define nd second +#define pb push_back +#define sz(x) (int)(x).size() +#define ll long long +ll mod=1000000007; +int inf=1000000007; +ll infl=1000000000000000007; + +int seg[4*600007]; +int lazy[4*600007]; +int pot=1; + +void push(int v,int sz) +{ + if(lazy[v]!=0) + { + seg[2*v]=sz/2*lazy[v]; + lazy[2*v]=lazy[v]; + seg[2*v+1]=sz/2*lazy[v]; + lazy[2*v+1]=lazy[v]; + } + lazy[v]=0; +} + +void ins(int u,int a,int b,int l,int r,int v) +{ + if(a<=l&&b>=r) + { + lazy[u]=v; + seg[u]=(r-l+1)*v; + return ; + } + if(l>b||r=r) return seg[u]; + if(l>b||rmapa; +int l[100007]; +int r[100007]; + +int main() +{ + ios_base::sync_with_stdio(0); + cin.tie(0); + cout.tie(0); + int n,h,ans=2; + cin>>n>>h; + setS; + S.insert(1); + S.insert(h); + for(int i=1;i<=n;i++) + { + cin>>l[i]>>r[i]; + l[i]++; + if(l[i]!=h) S.insert(l[i]+1); + if(l[i]!=1) S.insert(l[i]-1); + if(r[i]!=h) S.insert(r[i]+1); + if(r[i]!=1) S.insert(r[i]-1); + S.insert(l[i]); + S.insert(r[i]); + } + int it=0; + mapa.reserve(sz(S)+2); + for(auto x:S) mapa[x]=++it; + for(int i=1;i<=n;i++) + { + l[i]=mapa[l[i]]; + r[i]=mapa[r[i]]; + } + while(pot + +using namespace std; + +#define st first +#define nd second +#define pb push_back +#define sz(x) (int)(x).size() +#define ll long long +ll mod=1000000007; +int inf=1000000007; +ll infl=1000000000000000007; + +int a[77][77]; +int id[77][77]; +int id1[77][77]; +int id2[77][77]; +setG[15007]; +int cap1[3507][3507]; +unordered_mapcap[15007]; +int o[15007]; +bool odw[15007]; +int s=1,t; +char ans[77][77][3][3]; + +bool dfs(int v) +{ + //cout<>n>>m; + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + cin>>a[i][j]; + for(int k=0;k<3;k++) for(int l=0;l<3;l++) ans[i][j][k][l]='.'; + if(a[i][j]!=0) ans[i][j][1][1]='O'; + sum[(i+j)%2]+=a[i][j]; + } + } + if(sum[0]!=sum[1]) gg(); + edge(1,2,sum[0]); + int it=2; + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if(a[i][j]==0) continue; + id[i][j]=++it; + if(a[i][j]==2) + { + id1[i][j]=++it; + id2[i][j]=++it; + if((i+j)%2) + { + edge(id[i][j],id1[i][j],1); + edge(id[i][j],id2[i][j],1); + } + else + { + edge(id1[i][j],id[i][j],1); + edge(id2[i][j],id[i][j],1); + } + } + } + } + it+=2; + t=it; + edge(it-1,it,sum[0]); + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if(a[i][j]==0) continue; + if((i+j)%2) edge(2,id[i][j],a[i][j]); + else edge(id[i][j],it-1,a[i][j]); + } + } + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if((i+j)%2==0||a[i][j]==0) continue; + if(a[i-1][j]!=0) connect(i,j,i-1,j); + if(a[i+1][j]!=0) connect(i,j,i+1,j); + if(a[i][j-1]!=0) connect(i,j,i,j-1); + if(a[i][j+1]!=0) connect(i,j,i,j+1); + } + } + if(flow()!=sum[0]) gg(); + //cout< +using namespace std; + +typedef long long ll; +typedef long double ld; +typedef pair ii; +typedef vector vi; +typedef vector vii; +const int inf=0x3f3f3f3f; +const ll INF=0x3f3f3f3f3f3f3f3f; + +#define FOR(i, b, e) for(int i=b; i<=e; i++) +#define FORD(i, b, e) for(int i=b; i>=e; i--) +#define SIZE(x) ((int)x.size()) +#define pb push_back +#define st first +#define nd second +#define sp ' ' +#define ent '\n' + +ifstream out, wzor, in; + +int main(int argc, char *argv[]){ + assert(argc>=4); + + out.open(argv[1]); + wzor.open(argv[2]); + in.open(argv[3]); + + vector ans, user; + string pom; + while(wzor>>pom) ans.pb(pom); + while(out>>pom) user.pb(pom); + FOR(i, 1, 5) in>>pom; + + if(ans!=user) + { + if(pom != "0" && pom != "1" && pom != "3" && pom != "5"){ + cout << "Zla odpowiedz\n"; + exit(1); + } + int d=0, g=0, m=0, s=0; + FOR(i, 0, SIZE(ans)-1){ + if(ans[i][0]=='d') d=stoi(ans[i-1]); + if(ans[i][0]=='g') g=stoi(ans[i-1]); + if(ans[i][0]=='m') m=stoi(ans[i-1]); + if(ans[i][0]=='s') s=stoi(ans[i-1]); + } + if(SIZE(user)!=4 || stoi(user[0])!=d || stoi(user[1])!=g || stoi(user[2])!=m || stoi(user[3])!=s){ + cout << "Zla odpowiedz\n"; + exit(1); + } + } + + cout << "OK\n"; + exit(0); +} diff --git a/semestr-4/sieci/warsztaty8/dat0-check.e b/semestr-4/sieci/warsztaty8/dat0-check.e new file mode 100644 index 0000000..b0dcc41 Binary files /dev/null and b/semestr-4/sieci/warsztaty8/dat0-check.e differ diff --git a/semestr-4/sieci/warsztaty8/dat0-gen.sh b/semestr-4/sieci/warsztaty8/dat0-gen.sh new file mode 100644 index 0000000..a1640b1 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/dat0-gen.sh @@ -0,0 +1,107 @@ +#!/bin/bash + +echo -e "2019-01-08 00:00:00\n2019-01-09 00:00:00\n1" > dat1a.in +echo -e "2019-01-25 00:00:00\n2019-02-13 00:00:00\n1" > dat1b.in +echo -e "2019-01-25 00:00:00\n2019-03-13 00:00:00\n1" > dat1c.in +echo -e "2020-01-25 00:00:00\n2020-03-13 00:00:00\n1" > dat1d.in +echo -e "2000-01-25 00:00:00\n2000-03-13 00:00:00\n1" > dat1e.in +echo -e "2019-01-25 00:00:00\n2019-02-27 00:00:00\n1" > dat1f.in +echo -e "2019-01-25 00:00:00\n2019-03-27 00:00:00\n1" > dat1g.in +echo -e "2020-01-25 00:00:00\n2020-03-27 00:00:00\n1" > dat1h.in +echo -e "2000-01-25 00:00:00\n2000-03-27 00:00:00\n1" > dat1i.in +echo -e "2003-01-01 00:00:00\n2004-01-01 00:00:00\n1" > dat1j.in +echo -e "2004-01-01 00:00:00\n2005-01-01 00:00:00\n1" > dat1k.in +echo -e "2000-01-01 00:00:00\n2001-01-01 00:00:00\n1" > dat1l.in +echo -e "1999-01-01 00:00:00\n2000-01-01 00:00:00\n1" > dat1m.in +echo -e "1900-01-01 00:00:00\n2099-12-31 00:00:00\n1" > dat1n.in +echo -e "1945-04-17 00:00:00\n1974-01-17 00:00:00\n1" > dat1o.in +echo -e "2019-02-09 00:00:00\n2030-09-01 00:00:00\n1" > dat1p.in +echo -e "1992-11-13 00:00:00\n2049-01-13 00:00:00\n1" > dat1q.in + +echo -e "2019-01-08 00:00:00\n2019-01-09 00:00:00\n2" > dat2a.in +echo -e "2019-01-25 00:00:00\n2019-02-13 00:00:00\n2" > dat2b.in +echo -e "2019-01-25 00:00:00\n2019-03-13 00:00:00\n2" > dat2c.in +echo -e "2020-01-25 00:00:00\n2020-03-13 00:00:00\n2" > dat2d.in +echo -e "2000-01-25 00:00:00\n2000-03-13 00:00:00\n2" > dat2e.in +echo -e "2019-01-25 00:00:00\n2019-02-27 00:00:00\n2" > dat2f.in +echo -e "2019-01-25 00:00:00\n2019-03-27 00:00:00\n2" > dat2g.in +echo -e "2020-01-25 00:00:00\n2020-03-27 00:00:00\n2" > dat2h.in +echo -e "2000-01-25 00:00:00\n2000-03-27 00:00:00\n2" > dat2i.in +echo -e "2003-01-01 00:00:00\n2004-01-01 00:00:00\n2" > dat2j.in +echo -e "2004-01-01 00:00:00\n2005-01-01 00:00:00\n2" > dat2k.in +echo -e "2000-01-01 00:00:00\n2001-01-01 00:00:00\n2" > dat2l.in +echo -e "1999-01-01 00:00:00\n2000-01-01 00:00:00\n2" > dat2m.in +echo -e "1900-01-01 00:00:00\n2099-12-31 00:00:00\n2" > dat2n.in +echo -e "1945-04-17 00:00:00\n1974-01-17 00:00:00\n2" > dat2o.in +echo -e "2019-02-09 00:00:00\n2030-09-01 00:00:00\n2" > dat2p.in +echo -e "1992-11-13 00:00:00\n2049-01-13 00:00:00\n2" > dat2q.in + +echo -e "2000-01-01 00:00:00\n2000-01-01 00:00:01\n3" > dat3a.in +echo -e "2000-01-01 00:00:00\n2000-01-01 00:01:00\n3" > dat3b.in +echo -e "2000-01-01 00:00:00\n2000-01-01 01:00:00\n3" > dat3c.in +echo -e "2000-01-01 00:00:00\n2000-01-01 03:17:29\n3" > dat3d.in +echo -e "2000-01-01 00:00:00\n2000-01-01 19:15:59\n3" > dat3e.in +echo -e "2000-01-01 00:00:00\n2000-01-01 23:59:59\n3" > dat3f.in +echo -e "2000-01-01 00:00:01\n2000-01-01 00:01:00\n3" > dat3g.in +echo -e "2000-01-01 00:00:01\n2000-01-01 01:00:00\n3" > dat3h.in +echo -e "2000-01-01 00:00:01\n2000-01-01 03:17:29\n3" > dat3i.in +echo -e "2000-01-01 00:00:01\n2000-01-01 19:15:59\n3" > dat3j.in +echo -e "2000-01-01 00:00:01\n2000-01-01 23:59:59\n3" > dat3k.in +echo -e "2000-01-01 02:01:01\n2000-01-01 03:17:29\n3" > dat3l.in +echo -e "2000-01-01 04:01:01\n2000-01-01 19:15:59\n3" > dat3m.in +echo -e "2000-01-01 04:17:39\n2000-01-01 23:59:59\n3" > dat3n.in +echo -e "2000-01-01 02:01:57\n2000-01-01 03:17:29\n3" > dat3o.in + +echo -e "2000-01-01 00:00:00\n2000-01-01 00:00:01\n4" > dat4a.in +echo -e "2000-01-01 00:00:00\n2000-01-01 00:01:00\n4" > dat4b.in +echo -e "2000-01-01 00:00:00\n2000-01-01 01:00:00\n4" > dat4c.in +echo -e "2000-01-01 00:00:00\n2000-01-01 03:17:29\n4" > dat4d.in +echo -e "2000-01-01 00:00:00\n2000-01-01 19:15:59\n4" > dat4e.in +echo -e "2000-01-01 00:00:00\n2000-01-01 23:59:59\n4" > dat4f.in +echo -e "2000-01-01 00:00:01\n2000-01-01 00:01:00\n4" > dat4g.in +echo -e "2000-01-01 00:00:01\n2000-01-01 01:00:00\n4" > dat4h.in +echo -e "2000-01-01 00:00:01\n2000-01-01 03:17:29\n4" > dat4i.in +echo -e "2000-01-01 00:00:01\n2000-01-01 19:15:59\n4" > dat4j.in +echo -e "2000-01-01 00:00:01\n2000-01-01 23:59:59\n4" > dat4k.in +echo -e "2000-01-01 02:01:01\n2000-01-01 03:17:29\n4" > dat4l.in +echo -e "2000-01-01 04:01:01\n2000-01-01 19:15:59\n4" > dat4m.in +echo -e "2000-01-01 04:17:39\n2000-01-01 23:59:59\n4" > dat4n.in +echo -e "2000-01-01 02:01:57\n2000-01-01 03:17:29\n4" > dat4o.in + +echo -e "1917-06-04 13:25:19\n2045-04-19 11:17:39\n5" > dat5a.in +echo -e "1992-07-02 00:05:19\n2019-01-08 17:53:13\n5" > dat5b.in +echo -e "1900-01-01 00:00:00\n2099-12-31 23:59:59\n5" > dat5c.in +echo -e "1900-01-01 23:59:59\n2099-12-31 00:00:00\n5" > dat5d.in +echo -e "1959-10-13 17:14:40\n1965-10-25 19:10:53\n5" > dat5e.in +echo -e "2059-04-30 01:15:49\n2071-03-01 10:07:13\n5" > dat5f.in +echo -e "2010-02-19 20:49:10\n2061-02-28 15:40:49\n5" > dat5g.in + +echo -e "1917-06-04 13:25:19\n2045-04-19 11:17:39\n6" > dat6a.in +echo -e "1992-07-02 00:05:19\n2019-01-08 17:53:13\n6" > dat6b.in +echo -e "1900-01-01 00:00:00\n2099-12-31 23:59:59\n6" > dat6c.in +echo -e "1900-01-01 23:59:59\n2099-12-31 00:00:00\n6" > dat6d.in +echo -e "1959-10-13 17:14:40\n1965-10-25 19:10:53\n6" > dat6e.in +echo -e "2059-04-30 01:15:49\n2071-03-01 10:07:13\n6" > dat6f.in +echo -e "2010-02-19 20:49:10\n2061-02-28 15:40:49\n6" > dat6g.in + +echo -e "2010-10-10 11:59:59\n2010-11-02 10:22:21\n5" > dat5h.in +echo -e "1999-12-31 23:59:59\n2000-01-02 01:01:00\n5" > dat5i.in +echo -e "1985-01-15 21:55:53\n2009-11-12 23:21:10\n5" > dat5j.in +echo -e "2042-04-12 13:14:15\n2042-05-06 01:36:48\n5" > dat5k.in +echo -e "1931-01-01 23:01:58\n1931-01-01 23:59:58\n5" > dat5l.in +echo -e "2002-11-30 01:01:02\n2053-03-04 02:46:42\n5" > dat5m.in +echo -e "2022-02-22 22:59:23\n2022-03-01 04:03:26\n5" > dat5n.in +echo -e "1974-12-12 13:41:42\n2052-07-12 15:14:37\n5" > dat5o.in +echo -e "1922-12-31 23:59:59\n2022-01-02 00:00:00\n5" > dat5p.in + +echo -e "1997-01-12 22:59:23\n1997-02-15 00:01:26\n6" > dat6h.in +echo -e "1999-10-12 10:00:00\n2004-04-04 10:10:00\n6" > dat6i.in +echo -e "1923-03-14 11:22:53\n2009-11-12 11:21:34\n6" > dat6j.in +echo -e "2022-12-31 00:01:02\n2022-12-31 01:01:02\n6" > dat6k.in +echo -e "1988-11-11 12:11:59\n1989-01-01 11:10:02\n6" > dat6l.in +echo -e "2002-11-30 01:01:02\n2053-03-04 01:46:42\n6" > dat6m.in +echo -e "2022-02-22 22:59:23\n2022-03-01 03:03:26\n6" > dat6n.in +echo -e "1974-12-12 13:41:42\n2052-07-12 11:14:37\n6" > dat6o.in +echo -e "1922-12-31 23:59:59\n2022-01-02 20:00:00\n6" > dat6p.in + +g++ dat0-check.cpp -o dat0-check.e -O2 -std=c++11 diff --git a/semestr-4/sieci/warsztaty8/mie1.cpp b/semestr-4/sieci/warsztaty8/mie1.cpp new file mode 100644 index 0000000..f7eef7e --- /dev/null +++ b/semestr-4/sieci/warsztaty8/mie1.cpp @@ -0,0 +1,64 @@ +#include +#include +#include +using namespace std; + +#define EPS 0.000001 + +int main() { + int numLiquids, reqCon, liquid[101]; + double sumSubst=0, sumLiquid=0, actCon; + + fill(liquid,liquid+101,0); + + scanf("%d%d",&numLiquids,&reqCon); + + for (int i=0;i0)) { + double perc=(double)i/100, toSub=(double)((double)reqCon*sumLiquid-100*sumSubst)/((double)reqCon-(double)100*perc); + + toSub=min(toSub,(double)liquid[i]); + + sumLiquid-=toSub; + sumSubst-=(toSub*i)/100; + } + if ((actCon>(double)reqCon)&&(liquid[100-i]>0)) { + double perc=(double)(100-i)/100, toSub=(double)((double)reqCon*sumLiquid-100*sumSubst)/((double)reqCon-(double)100*perc); + + toSub=min(toSub,(double)liquid[100-i]); + + sumLiquid-=toSub; + sumSubst-=(toSub*(100-i))/100; + } + + if (sumLiquid==0) { + printf("0.000\n"); + return 0; + } + actCon=(sumSubst/sumLiquid)*100; + + if (fabs((double)reqCon-actCon) + +using namespace std; + +const int MAXN = 70; +int tab[MAXN][MAXN]; +char out[3*MAXN][3*MAXN]; +int N, M; + +int id(int x, int y, int strona){ //0 - prawo, 1 - g�ra, 2 - lewo, 3 - d�� + if(strona == 0){ + if(x+1 >= N) return -1; + if(tab[x+1][y] == 0) return -1; + if(tab[x+1][y] == 1) return 5*(MAXN*(x+1)+y); + if(tab[x+1][y] == 2) return 5*(MAXN*(x+1)+y); + if(tab[x+1][y] == 3) return 5*(MAXN*(x+1)+y)+2; + if(tab[x+1][y] == 4) return 5*(MAXN*(x+1)+y)+2; + } + if(strona == 1){ + if(y+1 >= M) return -1; + if(tab[x][y+1] == 0) return -1; + if(tab[x][y+1] == 1) return 5*(MAXN*x+y+1); + if(tab[x][y+1] == 2) return 5*(MAXN*x+y+1)+1; + if(tab[x][y+1] == 3) return 5*(MAXN*x+y+1)+3; + if(tab[x][y+1] == 4) return 5*(MAXN*x+y+1)+3; + } + if(strona == 2){ + if(x-1 < 0) return -1; + if(tab[x-1][y] == 0) return -1; + if(tab[x-1][y] == 1) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 2) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 3) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 4) return 5*(MAXN*(x-1)+y); + } + if(strona == 3){ + if(y-1 < 0) return -1; + if(tab[x][y-1] == 0) return -1; + if(tab[x][y-1] == 1) return 5*(MAXN*x+y-1); + if(tab[x][y-1] == 2) return 5*(MAXN*x+y-1)+1; + if(tab[x][y-1] == 3) return 5*(MAXN*x+y-1)+1; + if(tab[x][y-1] == 4) return 5*(MAXN*x+y-1)+1; + } +} + +set real_v; +vector edges[5*MAXN*MAXN+5]; +int match[5*MAXN*MAXN+5]; +bool mark[5*MAXN*MAXN+5]; +bool dfs(int v){ + if(real_v.count(v) == 0) return false; + if(mark[v]) return false; + mark[v] = true; + for(auto &u : edges[v]) + if(match[u] == -1 || dfs(match[u])) + return match[v] = u, match[u] = v, true; + return false; +} + +int main(){ + cin >> N >> M; + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + cin >> tab[i][j]; + } + } + + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + if(tab[i][j] == 1){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)); + } + if(tab[i][j] == 2){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+(k%2)].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1); + } + if(tab[i][j] == 3){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+k].push_back(id(i, j, k)); + edges[5*(MAXN*i+j)+k].push_back(5*(MAXN*i+j)+4); + edges[5*(MAXN*i+j)+4].push_back(5*(MAXN*i+j)+k); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1), real_v.insert(5*(MAXN*i+j)+2), real_v.insert(5*(MAXN*i+j)+3), real_v.insert(5*(MAXN*i+j)+4); + } + if(tab[i][j] == 4){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+k].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1), real_v.insert(5*(MAXN*i+j)+2), real_v.insert(5*(MAXN*i+j)+3); + } + } + } + + /*for(int i = 0; i < 5*MAXN*MAXN+5; i++){ + if(!edges[i].empty()){ + cerr << "Edges of " << i << ": "; + for(int v : edges[i]) cerr << v << " "; + cerr << "\n"; + } + }*/ + + for(int i = 0; i < 5*MAXN*MAXN+5; i++) match[i] = -1; + for(int i = 0; i < 5*MAXN*MAXN+5; i++) + if(match[i] == -1){ + memset(mark, false, sizeof mark); + dfs(i); + } + + for(int i : real_v) if(match[i] == -1){ + cout << "NIE"; + return 0; + } + + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + if(tab[i][j] == 1){ + int str; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)] == id(i, j, k)){ + str = k; + } + out[3*i+1][3*j+1] = 'O'; + if(str == 0) out[3*i+2][3*j+1] = 'X'; + if(str == 1) out[3*i+1][3*j+2] = 'X'; + if(str == 2) out[3*i][3*j+1] = 'X'; + if(str == 3) out[3*i+1][3*j] = 'X'; + } + if(tab[i][j] == 2){ + int strh, strv; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)] == id(i, j, k)){ + strh = k; + } + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)+1] == id(i, j, k)){ + strv = k; + } + out[3*i+1][3*j+1] = 'O'; + if(strh == 0) out[3*i+2][3*j+1] = 'X'; + if(strv == 1) out[3*i+1][3*j+2] = 'X'; + if(strh == 2) out[3*i][3*j+1] = 'X'; + if(strv == 3) out[3*i+1][3*j] = 'X'; + } + if(tab[i][j] == 3){ + int str; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)+4] == 5*(MAXN*i+j)+k){ + str = k; + } + out[3*i+1][3*j+1] = 'O'; + out[3*i+2][3*j+1] = 'X'; + out[3*i+1][3*j+2] = 'X'; + out[3*i][3*j+1] = 'X'; + out[3*i+1][3*j] = 'X'; + if(str == 0) out[3*i+2][3*j+1] = '.'; + if(str == 1) out[3*i+1][3*j+2] = '.'; + if(str == 2) out[3*i][3*j+1] = '.'; + if(str == 3) out[3*i+1][3*j] = '.'; + } + if(tab[i][j] == 4){ + out[3*i+1][3*j+1] = 'O'; + out[3*i+2][3*j+1] = 'X'; + out[3*i+1][3*j+2] = 'X'; + out[3*i][3*j+1] = 'X'; + out[3*i+1][3*j] = 'X'; + } + } + } + + for(int i = 0; i < 3*N; i++){ + for(int j = 0; j < 3*M; j++){ + if(!out[i][j]) cout << "."; + else cout << out[i][j]; + } + cout << "\n"; + } +} diff --git a/semestr-4/sieci/warsztaty8/prz9.cpp b/semestr-4/sieci/warsztaty8/prz9.cpp new file mode 100644 index 0000000..952daac --- /dev/null +++ b/semestr-4/sieci/warsztaty8/prz9.cpp @@ -0,0 +1,97 @@ +// solution written by Michal 'misof' Forisek +#include +#include +#include +#include +using namespace std; + +#define FOREACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) + +class MaximumMatching { + int left_size, right_size; + vector< vector > right_to_left; + + public: + MaximumMatching() { left_size=right_size=0; right_to_left.clear(); } + void add_edge(int left, int right); + vector< pair > maximum_matching(); +}; + +void MaximumMatching::add_edge(int left, int right) { + if (left==-1 || right==-1) return; + if (left_size <= left) left_size = left+1; + if (right_size <= right) { right_size = right+1; right_to_left.resize(right_size); } + right_to_left[right].push_back(left); +} + +vector< pair > +MaximumMatching::maximum_matching() { + int L = left_size, R = right_size; + vector match(L,-1); + for (int r=0; r from(L,-1); + queue Q; + FOREACH(it,right_to_left[r]) { Q.push(*it); from[*it]=*it; } + while (!Q.empty() && !found) { + int l = Q.front(); Q.pop(); + if (match[l]==-1) { + found = true; + while (from[l]!=l) { match[l] = match[from[l]]; l = from[l]; } + match[l]=r; + } else { + FOREACH(it,right_to_left[ match[l] ]) if (from[*it]==-1) { Q.push(*it); from[*it]=l; } + } + } + } + vector< pair > result; + for (int i=0; i > A; // the map of the island + +int ENCODE(int r, int c, int n) { return (C*r+c)*5+n; } +int LEFT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,1); } +int RIGHT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,3); } +int TOP(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]==2) return ENCODE(r,c,1); else return ENCODE(r,c,0); } +int BOTTOM(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,A[r][c]-1); else return ENCODE(r,c,2); } +#define VERTEX(r,c,dir) ( ((r<0) || (c<0) || (r>=R) || (c>=C)) ? -1 : dir(r,c) ) + +int main() { + // read the input + cin >> R >> C; + A.resize(R, vector(C) ); + for (int r=0; r> A[r][c]; + + // create the bipartite graph + MaximumMatching MM; + for (int r=0; r > matching = MM.maximum_matching(); + if (2*matching.size() != expected_size) { cout << "NIE" << endl; return 0; } + + // from the edges of the matching, reconstruct the map + set< pair > edges; + FOREACH(it,matching) { edges.insert(make_pair(it->first,it->second)); edges.insert(make_pair(it->second,it->first)); } + vector output(3*R, string(3*C,'.')); + for (int r=0; r +#include +using namespace std; +#define rand_mod 1000000033 +int rozm, zapy, ds[200000], dl; +typedef long long LL; +LL sum, wcz[200000], rand_plus, ele[6]; +bool cmp(int x, int y) +{ + return wcz[x] < wcz[y]; +} +int main() +{ + scanf("%d%Ld", &rozm, &rand_plus); + scanf("%d", &zapy); + for (int i = 0; i < zapy; ++i) + { + scanf("%Ld%Ld", wcz + 2 * i, wcz + 2 * i + 1); + --wcz[2 * i]; + } + for (int i = 0; i < 2 * zapy; ++i) + ds[i] = i; + sort(ds, ds + 2 * zapy, cmp); + while (dl < 2 * zapy && !wcz[ds[dl]]) + ++dl; + + for (int i = 1; i <= rozm; ++i) + { + ele[0] = (ele[1] * ele[1]) % rand_mod; + ele[0] += ((ele[2] + ele[3]) * (ele[2] + ele[3])) % rand_mod; + ele[0] += (ele[4] * ele[5]) % rand_mod; + ele[0] += (rand_plus * rand_plus) % rand_mod; + ele[0] += i % rand_mod; + ele[0] %= rand_mod; + sum += ele[0]; + while (dl < 2 * zapy && wcz[ds[dl]] == i) + wcz[ds[dl++]] = sum; + for (int i = 4; i >= 0; i--) ele[i+1] = ele[i]; + ele[0] = 0; + } + for (int i = 0; i < zapy; ++i) + printf("%Ld\n", wcz[2 * i + 1] - wcz[2 * i]); + return 0; +} diff --git a/semestr-4/sieci/warsztaty8/w8.pdf b/semestr-4/sieci/warsztaty8/w8.pdf new file mode 100644 index 0000000..91676f4 Binary files /dev/null and b/semestr-4/sieci/warsztaty8/w8.pdf differ diff --git a/semestr-4/sieci/warsztaty8/wie5.cpp b/semestr-4/sieci/warsztaty8/wie5.cpp new file mode 100644 index 0000000..0821777 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/wie5.cpp @@ -0,0 +1,158 @@ +#include + +using namespace std; +typedef long long ll; + +mt19937 rng(rand()); +const int MAXDEG = 10000; +long long poly[MAXDEG+1]; +int deg; + +int gcd(int a, int b){ + return !b ? a : gcd(b, a%b); +} + +struct rat{ + int sign; + int num, den; + + void cancel(){ + int d = gcd(num, den); + this->num /= d; + this->den /= d; + } + + rat(int a, int b){ + this->sign = 1; + if(a == 0){ + this->sign = 0; + this->num = 0; + this->den = 1; + return; + } + if(b < 0){ + this->sign = -1; + } + this->den = abs(b); + if(a < 0){ + this->sign = -(this->sign); + } + this->num = abs(a); + cancel(); + } + + bool operator<(const rat &x) const { + if(this->sign != x.sign) return this->sign < x.sign; + + bool abs_less; + long long int left = (long long)(this->num) * (long long)(x.den); + long long int right = (long long)(x.num) * (long long)(this->den); + abs_less = left < right; + + if(left == right) return false; + if(this->sign == -1) return !abs_less; + if(this->sign == 0) return false; + if(this->sign == 1) return abs_less; + } + + bool operator==(const rat &x) const { + return this->sign == x.sign && this->num == x.num && this->den == x.den; + } + + friend ostream& operator<<(ostream &stream, const rat &x){ + if(x.sign == -1) stream << '-'; + stream << x.num << "/" << x.den; + return stream; + } +}; + +ll W(rat x, int mod){ + ll out = 0; + ll den_pow = 1; + ll num = x.num; + ll den = x.den; + if(x.sign == -1) num = mod-num; + for(int i = deg; i >= 0; i--){ + out += (poly[i]*den_pow)%mod; + if(i) out *= num; + out %= mod; + den_pow = (den_pow * den)%mod; + } + //cerr << x << " " << mod << " " << out << endl; + return out; +} + +bool check(rat x){ + for(int i = 0; i < 20; i++){ + int p = uniform_int_distribution(2, 1000000000)(rng); + if(W(x, p)){ + //cerr << x << " " << p << endl; + return false; + } + } + return true; +} + +vector< int > nums; +vector< int > dens; +vector< rat > candidates_mult; +vector< rat > candidates; +void cands(){ + for(int i = 1; i*i <= abs(poly[0]); i++){ + if(abs(poly[0]) % i) continue; + nums.push_back(i); + nums.push_back(-i); + nums.push_back(poly[0]/i); + nums.push_back(-poly[0]/i); + } + + for(int i = 1; i*i <= abs(poly[deg]); i++){ + if(abs(poly[deg]) % i) continue; + dens.push_back(i); + dens.push_back(poly[deg]/i); + } + + //cerr << nums.size() << " * " << dens.size() << " = " << (nums.size())*(dens.size()) << endl; + + for(int p : nums){ + for(int q : dens){ + candidates_mult.push_back({p, q}); + } + } + sort(candidates_mult.begin(), candidates_mult.end()); + candidates.push_back(candidates_mult[0]); + for(int i = 1; i < candidates_mult.size(); i++){ + if(!(candidates_mult[i-1] == candidates_mult[i])){ + candidates.push_back(candidates_mult[i]); + } + } + + //for(rat r : candidates) cerr << r << endl; +} + +vector< rat > s; +void solve(){ + if(!poly[0]){ + s.push_back({0, 1}); + int k = 0; + while(poly[k] == 0) k++; + for(int i = 0; i <= deg-k; i++) poly[i] = poly[i+k]; + deg -= k; + } + + cands(); + for(rat c : candidates) if(check(c)) s.push_back(c); + sort(s.begin(), s.end()); + cout << s.size() << "\n"; + for(rat i : s) cout << i << " "; +} + +int main(){ + ios_base::sync_with_stdio(0); + cin.tie(0); + cout.tie(0); + + cin >> deg; + for(int i = 0; i <= deg; i++) cin >> poly[deg-i]; + solve(); +} diff --git a/semestr-4/sieci/warsztaty8/wie5.pdf b/semestr-4/sieci/warsztaty8/wie5.pdf new file mode 100644 index 0000000..cd5637b Binary files /dev/null and b/semestr-4/sieci/warsztaty8/wie5.pdf differ diff --git a/semestr-4/sieci/wyklady/ASD_kol2_2021-1.pdf b/semestr-4/sieci/wyklady/ASD_kol2_2021-1.pdf new file mode 100644 index 0000000..2fbe591 Binary files /dev/null and b/semestr-4/sieci/wyklady/ASD_kol2_2021-1.pdf differ diff --git a/semestr-4/sieci/wyklady/lec1.pdf b/semestr-4/sieci/wyklady/lec1.pdf new file mode 100644 index 0000000..5da8f03 Binary files /dev/null and b/semestr-4/sieci/wyklady/lec1.pdf differ diff --git a/semestr-4/sieci/wyklady/lec13.pdf b/semestr-4/sieci/wyklady/lec13.pdf new file mode 100644 index 0000000..245259f Binary files /dev/null and b/semestr-4/sieci/wyklady/lec13.pdf differ diff --git a/semestr-4/sieci/wyklady/lec2.pdf b/semestr-4/sieci/wyklady/lec2.pdf new file mode 100644 index 0000000..edb1398 Binary files /dev/null and b/semestr-4/sieci/wyklady/lec2.pdf differ diff --git a/semestr-4/sieci/wyklady/lec3.pdf b/semestr-4/sieci/wyklady/lec3.pdf new file mode 100644 index 0000000..ae48ec2 Binary files /dev/null and b/semestr-4/sieci/wyklady/lec3.pdf differ diff --git a/semestr-4/sieci/wyklady/lec4.pdf b/semestr-4/sieci/wyklady/lec4.pdf new file mode 100644 index 0000000..352b71d Binary files /dev/null and b/semestr-4/sieci/wyklady/lec4.pdf differ diff --git a/semestr-4/sieci/wyklady/lec5.pdf b/semestr-4/sieci/wyklady/lec5.pdf new file mode 100644 index 0000000..3a7b39b Binary files /dev/null and b/semestr-4/sieci/wyklady/lec5.pdf differ diff --git a/semestr-4/sieci/wyklady/lec6.pdf b/semestr-4/sieci/wyklady/lec6.pdf new file mode 100644 index 0000000..04975ce Binary files /dev/null and b/semestr-4/sieci/wyklady/lec6.pdf differ diff --git a/semestr-4/sieci/wyklady/lec7.pdf b/semestr-4/sieci/wyklady/lec7.pdf new file mode 100644 index 0000000..0b28c4d Binary files /dev/null and b/semestr-4/sieci/wyklady/lec7.pdf differ diff --git a/semestr-4/sieci/wyklady/lec8.pdf b/semestr-4/sieci/wyklady/lec8.pdf new file mode 100644 index 0000000..a4fbb9c Binary files /dev/null and b/semestr-4/sieci/wyklady/lec8.pdf differ -- cgit v1.2.3